For循環通過遞增變量，時間複雜性

for (int i = 1; i < a; i++){ 
    for(int j = 1; j < b; j = j + a){ 
     Function() <-- O(1) 
    } 
}

在這種情況下，外循環將執行B/A‘次「a'times（O（A）），和內循環將執行’（ O（b/A））。For循環通過遞增變量，時間複雜性

那麼總的時間複雜度將是O（a * b/a）= O（b）？

我不是這種解釋是正確的或不..

2017-01-18 NoSleep

可能重複[大O，你如何計算/近似它？]（http://stackoverflow.com/questions/3255/big-o-how-do-you-calculate-approximate-it） –

爲什麼內循環會執行'b/a'次嗎？你可能混合了一些東西：循環本身重複'b'次（'Function（）'）並且它本身（'for（int j = 1 ...）{...}'）重複'a'次。 – Paul

@Paul我編輯了內部循環。請再檢查一次。 – NoSleep

好O(a * b/a) = O(b)顯然是正確的，因爲有身份在那裏：O(b*a/a) = O(b*1) = O(b)。

但是，它的時間複雜度似乎是O(a*b*1)（假設循環不會導致時間上的開銷）。計算工作量隨每個單獨的循環大小線性增加。這是O(a*b)的原因。

2017-01-18 01:37:54

內循環有錯字請再次檢查 – NoSleep

阿門是正確的，答案是O（ab）。我們可以得到這些步驟的答案：

O（（A-1）（B-1）（1））

= O（AB-AB + 1），其中-A-B +1可以被忽略。

= O（AB）

2017-01-18 02:01:16 Tim

我編輯了內循環，請再次檢查 – NoSleep

我認爲這是一個很好的問題，我的想法是

原來的複雜性應該是O(a) * O(b/a)

但是你跳進結論之前，你必須判斷例：

如果b <= a，然後O(b/a) = O(1)，所以O(a) * O(b/a) = O(a)

如果b > a，然後O(b/a) = O(b/a)，所以O(a) * O(b/a) = O(b)

所以結合這些情況下，我會說這是O(max(a,b))

2017-01-18 09:43:42 shole

O(b)是不正確，因爲你穿過外環a倍，因此答案必須至少爲O(a)（並且，對於你所知道的，b可能比a小得多）。答案應該僅取決於a和b而不僅僅取決於b。

仔細計數，則通過內環路ceil((b-1)/a)倍，因此複雜性是

O(a*ceil((b-1)/a))

但是，

ceil((b-1)/a) <= (b-1)/a + 1

因此

a*ceil((b-1)/a) <= a*((b-1)/a + 1) = b - 1 + a = a + b - 1

的1是漸近可忽略不計，因此複雜性是O(a+b)。

由於O(a+b) = O(max(a,b))這與@shole的答案一致。

2017-01-18 11:22:26

回答