1

我将如何判断我的代码是否在 O(N) 时间（线性时间？）或 O(N^2) 时间或其他时间运行？为需要很长时间计算的代码练习测试在线停靠点。

我知道最好有一个脚本，其中运行所需的时间仅与输入数据的长度成正比（ O(N) 时间），我想知道这是否是我的代码正在做的事情。又如何知道代码运行的速度有多快？

下面我包括了一个我写的我关心的脚本。它来自一个练习考试问题，其中给你一系列'a'和'b'，你要计算回文。因此，如果给定 s = "baababa"，则有 6 个回文：'aa'、'baab'、'aba'、'bab'、'ababa' 和 'aba'。

def palindrome(s):
  length = len(s)
  last = len(s)-1
  count = 0

  for index, i in enumerate(s):
    left=1
    right=1
    left2=1
    right2=1

    for j in range(0,index+1): #+1 because exclusive
      if index-left2+1>=0 and index+right2<=last and s[index-left2+1]==s[index+right2]:
        print s[index-left2+1:index+right2+1] #+1 because exclusive
        left2 +=1
        right2 +=1
        count +=1

      elif index-left>=0 and index+right<=last and s[index-left] == s[index+right]:
        print s[index-left:index+right+1] #+1 because exclusive
        left += 1
        right +=1
        count += 1

  return count

这是 O(N) 时间吗？我只遍历整个列表一次，但也有一个较小的循环......

4

3 回答 3

3

它是 O(N^2)。您有一个从 0 到 N 的循环，第二个循环从 0 到 i。让我们看看您必须执行多少操作。对于每个“i”，我们查看 j 从 0 到 i + 1 的列表大小（让我们取 N = 7）：

i = 0 | x x _ _ _ _ _ _  -
i = 1 | x x x _ _ _ _ _  |
i = 2 | x x x x _ _ _ _  |
i = 3 | x x x x x _ _ _  N
i = 4 | x x x x x x _ _  |
i = 5 | x x x x x x x _  |
i = 6 | x x x x x x x x  _
       |-----N + 1-----|

整个矩形的面积是~N * N（实际上是N * (N + 1)，但是这里没那么重要），所以我们看到有~N ^ 2 / 2个操作。它是 O(N^2)。

于 2013-07-21T18:49:36.713 回答
3

好吧，让我们考虑一下。输入的大小是n = len(s)。对于每个字符，您从 0 循环到索引。所以我们可以得到以下

for i = 0 to n
    for j = 0 to i + 1
        1

可以简化为

for i = 0 to n
    (i + 1)(i + 2)

然后给了我们

for i = 0 to n
    i^2 + 3i + 2

然后我们可以将它拆分并减少它，我们知道它 3i + 2会立即减少到3(n)(n + 1) + 2n = 3n^2 + 5n哪个不是线性的，因为它是 O(n^2)。我也不明白通过第二个 for 循环你在做什么，你可以通过比较最后一个字符和第一个字符来计算线性时间的回文。

如果您想知道如何：http ://rosettacode.org/wiki/Palindrome_detection#Python

于 2013-07-21T18:50:05.713 回答
1

这不是 O(N) 时间。尽管您只循环enumerate(s)一次数组。在每个循环中，您都会做一些额外的工作。让我们假设数组的长度为 N。因此，重复的总数将大约为 1+2+3+..+N，即 N*(N+1)/2，简化为 O(N ^2) 运行时间。

于 2013-07-21T18:53:18.913 回答