算法的運行時間計算/複雜度

我必須逐行計算算法的時間複雜度或理論運行時間（假定爲psuedocode）T（n）。我試了一下，但有幾件事讓我感到困惑。例如，「if」語句的時間複雜度是多少？我該如何處理嵌套循環？代碼如下，以及我評論的嘗試。算法的運行時間計算/複雜度

長度[A] = N

for i = 0 to length[A] - 1 // n - 1 
     k = i + 1     // n - 2 
     for j = 1 + 2 to length[A] // (n - 1)(n - 3) 
     if A[k] > A[j]   // 1(n - 1)(n - 3) 
      k = j     // 1(n - 1)(n - 3) 
     if k != i + 1    // 1(n - 1) 
     temp = A[i + 1]   // 1(n - 1) 
     A[i + 1] = A[k]   // 1(n - 1) 
     A[k] = temp    // 1(n - 1)

來源

2013-01-22 aclark

我得到了'O（n^2）'。您的'if'語句可以忽略，因爲它不會改變循環的流程。你的內循環不依賴於外循環，所以它們爲給定的'n'運行'（n - a）*（n - b）= n^2 + ...'次。 – Blender

我的歉意。我將來不會使用該標籤。 – aclark

攪拌機是正確的，其結果爲O（n^2）：兩個嵌套循環，即每一個都具有重複計數依賴n。

更詳細的解釋：

的，如果在這種情況下，沒有真正的問題：由於O型符號只着眼於算法的最壞情況下的執行時間，你只需選擇的執行路徑總體執行時間更差。因爲在你的例子中，兩個執行路徑（k != i+ 1是true或false）對於運行時沒有進一步的含義，你可以忽略它。如果有第三個嵌套循環，也運行到n，在if的內部，你最終會得到O（n^3）。

甲線由行概述：

for i = 0 to length[A] - 1 // n + 1 [1] 
    k = i + 1     // n 
    for j = 1 + 2 to length[A] // (n)(n - 3 + 1) [1] 
    if A[k] > A[j]   // (n)(n - 3) 
     k = j     // (n)(n - 3)*x [2] 
    if k != i + 1    // n 
    temp = A[i + 1]   // n*y [2] 
    A[i + 1] = A[k]   // n*y 
    A[k] = temp    // n*y

[1] for循環語句將用下面的值來執行N + 1次i：0（真，繼續循環），1（ true，continue循環），...，length[A] - 1（true，繼續循環），length[A]（false，break循環）

[2]如果不知道數據，則必須猜測if的條件爲真。 x是獨立的n，從而影響整體運行的複雜性只是作爲一個常數因子：你需要採取這種猜測可以用數學通過引入變量0 < = x < = 1。這是符合我說的話之前完成看執行路徑。

來源

2013-01-23 12:12:17 rainer

算法的運行時間計算/複雜度

回答

相關問題