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）時間？

回答

相關問題