arrays - 我如何改变算法以获得更好的渐近复杂度？

Question

伙计们。

我有一个时机很好的算法，我应该改变它以获得更好的时间，但我不知道。

你能帮我吗？

这是时间：

• 实际0m0.164s
• 用户 0m0.021s
• 系统 0m0.010s

这是算法：

def algo2(A, B):
    x=0
    y=0
    for a in A:
          m=0
          for b in B:
                if a == b:
                      m += 1
          if m>y:
                x = a
                y = m
    return x;

这是算法的数组：
A = [1,2,3,4,5,6,7,8,9,0] B = [1,2,3,4,5,6,4,7,8, 9,0]

Answer 1

你的算法是 O(n*m)。如果数组总是排序的，你可以直接合并（O（n+m）），如下所示。（注意代码不是python……我想你可以理解并翻译它）

ixA = 0
ixB = 0
maxVal = 0
maxCount = 0
workingVal = A[ixA]
workingCount = 0
while (ixA < A.length and ixB < B.length)
{
    if (workingVal == B[ixB])
    {
        workingCount += 1
    }
    else if (workingCount > maxCount)
    {
        maxCount = workingCount
        maxVal = workingVal
        workingCount = 0
        ixA += 1
        workingVal = A[ixA]
    }
    ixB += 1
}
// have to check the last one
if (workingCount > maxCount)
{
    maxCount = workingCount
    maxVal = workingVal
}

如果数组没有排序，你可以先排序，然后合并。这将是 O(m log m) + O(n log n) + O(m+n)。这仍然比你的 O(m*n) 好。