Python脚本：如何判断在O（N）或O（N^2）时间？

我该怎么去告诉我的代码是在O（N）时间（线性时间？）还是O（N^2）时间或其他东西上运行？练习测试在线码头点以计算需要很长时间的代码。Python脚本：如何判断在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）时间吗？我只遍历整个列表一次，但有一个更小的循环以及...

来源

2013-07-21 natsuki_1996

它是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 + 1），但在这里并没有多大关系），所以我们看到有〜N^2/2的操作。它是O（N^2）。

来源

2013-07-21 18:49:36

对不起，罗马，我不明白你的图。请提供简短的解释吗？ –

稍微改了一个答案，如果还不够，我会尽力在后面写更详细的解释 –

谢谢！现在有很多意义！ –

好吧，让我们考虑一下。输入的大小是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）。我也不明白你在做什么，通过第二个循环，你可以通过比较最后和第一个字符，以线性时间计算回文。

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

来源

2013-07-21 18:50:05 Ford

谢谢！起初很复杂，但最终得到它！ –

这不是O（n）的时间。尽管您只需循环访问enumerate(s)阵列一次。在每个循环中，你都会做一些额外的工作让我们假设阵列的长度为N.因此，重复的总数将近似为1 + 2 + 3 + ... + N，其为N *（N + 1）/ 2，其简化为O（N^2）运行时间。

来源

2013-07-21 18:53:18

谢谢！阵列对我有帮助！ –

Python脚本：如何判断在O（N）或O（N^2）时间？

回答

相关问题