2017-06-14 82 views
0

我需要幫助計算代碼片段時間複雜度的步驟數。計算代碼步驟數(時間複雜度)

total = 0 
    i = 0 
while i<3: 
    j=0 
    while j<3: 
     total = total + 1 
     j = j+1 
    i = i+1 
return total 

我有解決方案說明:2 + 3 *(2 + 3 * 3 + 2)2 = 43

從頂部的前兩行,其中總= 0且i = 0,是的,我知道他們每個人都是1個時間步,因此總共給了我2個。對於while語句,我不確定它是如何獲得的,但是因爲我的3步時間?然後j = 0是1個時間步長。

現在,這裏是我不明白的地方。如果存在嵌套的i和j循環,我如何確定時間複雜度?在解決方案中,我注意到有*(多個),如果有人可以用簡單的術語來分解我,我會很感激。

回答

1

時間複雜性需要一個參數。例如,O(n^2)。因爲它的寫法,我不知道你的函數的哪個部分會改變,所以它只是不變的,O(1)。

讓我們說i相比,在這種情況下,3是可以改變的。就像你的功能是「每個我做三次j」。在這種情況下,你會看到如果你增加了這個變量,你會在循環中增加三個步驟。這意味着複雜性看起來像O(3n)。由於我們可以刪除常數倍數,所以它只是O(n)。

雖然我剛剛寫的是假設的。這取決於你的功能有什麼不同。