Python 脚本 : How to tell if in O(N) or O(N^2) time

我如何判断我的代码是按 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) 时间吗？我只遍历整个列表一次，但还有一个较小的循环...

请您参考如下方法:

它是 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)。