如何改变算法以获得更好的渐近复杂性？

我有一个很好的时间算法，我应该改变它以获得更好的时间，但我没有任何想法。

你能帮助我吗？

这里是时间：

真正0m0.164s
用户0m0.021s
SYS 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]

来源

2013-03-25 Gudron

数组中的值是否存在绑定？数组是否总是排序？ – beaker 2013-03-25 14:05:18

算法做什么？ – SomeWittyUsername 2013-03-25 14:08:45

我想A中的元素是唯一的，但不是B中的。你想在A中找到最常出现在A中的元素.n是A中元素的数量，m是B中元素的数量，你的算法是O（纳米）。获得更好的大O的方法是对A和B进行排序，然后线性浏览A和B，得到O（n.log n + m.log m + n + m） – Kwariz 2013-03-25 14:11:30

你的算法是O（n * m）。如果数组总是被排序，则可以进行直接合并（O（n + m）），如下所示。（请注意，代码是不是蟒蛇......我想你可以得到的想法，并把它翻译）

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）还要好。

来源

2013-03-25 14:04:27

如何改变算法以获得更好的渐近复杂性？

回答

相关问题