確定最壞情況算法的時間複雜性

這兩種算法是否具有Θ（n^2）的相同θ表徵？確定最壞情況算法的時間複雜性

int sum = 0; 
for (int i = 0; i < n; i++) 
    for (int j = 0; j < n * n; j++) 
     sum++; 

int sum = 0; 
for (int i = 0; i < n; i++) 
    for (int j = 0; j < i; j++) 
     sum++;

如果不是那麼這是否意味着這種表徵不是Θ（n^3）？

int sum = 0; 
for (int i = 0; i < n; i++) 
    for (int j = 0; j < i * i; j++) 
     for (int k = 0; k < j; k++) 
      sum++;

來源

2010-09-29 Dan

您怎麼看？ – aaronasterling 2010-09-29 02:30:20

我不認爲是第一個，但是對於j <我是n^2，但我不知道爲什麼 – Dan 2010-09-29 02:35:09

你會如何計算兩者中的任何一個所採取的步驟？第二個是 – aaronasterling 2010-09-29 02:37:36

@丹，這是第一個你真正的意思j < n * n而非j < n？如果是這樣，第一個的時間複雜度是Θ（n^3），不是嗎？如果你的意思是j < n，那麼我相信前兩個都是Θ（n^2）：第一個需要n^2個步驟，第二個需要1 + 2 + ... + n = n（ n + 1）/ 2，即Θ（n^2）。

我在想第三個是Θ（n^4），但它很難證明。當然是O（n^4）。

來源

2010-09-29 02:56:47 LarsH

是的，我的意思是j Dan 2010-09-29 03:21:43

@Dan乘法運算n增加了n，而不是1. for（int i = 0; i 2010-09-29 03:33:25

@Tan當@Dan表示學位時我相信他在談論指數。所以是的@Dan如果你乘n^k * n，你會得到n ^（k + 1）。我不確定這是不是你問的問題。 – LarsH 2010-09-29 05:07:48

確定最壞情況算法的時間複雜性

回答

相關問題