以下簡單程序的複雜程度如何？

-4

我無法找到理解複雜性。有人能幫助我理解下面代碼的複雜性是什麼以及爲什麼。以下簡單程序的複雜程度如何？

for (int i = 1; i < n; i++) { // (n is a number chosen by the user) 
    for (int j = i - 1; j >= 0; j--) { 
     printf("i=%d, j=%d", i, j); 
    } 
}

解釋會很好。

來源

2016-03-07 J. Doe

你認爲這是什麼，你有什麼麻煩？你知道如何估計任何*程序的「複雜性」嗎？ – juanchopanza

'i'的初始值是多少？ – Frodo

你認爲*複雜性是什麼？爲什麼你這麼想？ –

原始的問題：因爲i的初始值是未定義的，該代碼的行爲是不可預測的。除了複雜性未定義之外，沒有辦法有效地回答這個問題。沒有辦法知道代碼將執行多少操作。

更新的問題：這是O（1）。代碼將始終執行完全相同的工作量。

來源

2016-03-07 07:56:34

對不起。我修好了。 –

你沒有修復它，你做了一個完全不同的問題。 –

您可以通過評估操作的次數，即調用到printf()數計算這個代碼片段的時間複雜度，其爲簡單起見，我們將假設是等價的：

在1假設i開始（你最初忘了初始化它），外部循環運行99次，對於每次迭代，內部循環運行i次。當他計算迭代的結果數爲99 * (99 + 1)/2時，高斯據說9歲。

的原片的代碼的複雜性O（1），因爲它不依賴於任何變量，但因爲不是你更新的代碼爲：

void fun(int n) { 
    for (int i = 1; i < n; i++) { 
     for (int j = i - 1; j >= 0; j--) { 
      printf("i=%d, j=%d", i, j); 
     } 
    } 
}

的時間複雜度會出來作爲O（n ）。

來源

2016-03-07 08:00:16 chqrlie

高斯和方程爲'n *（n + 1）/ 2'，所以如果n = 100，則迭代次數爲4950。 – Frodo

@弗羅多：謝謝你......我真的不是高斯。 – chqrlie

假設我從0開始，複雜度將是恆定的。複雜度總是相對於定義執行次數的變量來表示的，這在這裏不是這種情況。

如果應該用一個術語來描述這種行爲，那麼它是「不變的」。將會有一些處決，但這個數字永遠不會改變

來源

2016-03-07 08:00:30 Houbie

以下簡單程序的複雜程度如何？

回答

相關問題