簡單的時間複雜度計算

Question

我是新來的時間複雜性，現在開始解決問題， 我不確定我是否正確，請告訴我，如果我這樣做，如果沒有， 如何計算它。

我計算的最壞情況下6n+5，而一般情況下，O(n)，是正確的嗎？

Answer 1

採取最常執行的指令。這是num = Random.Next (100)（與其他人並列）。它多久執行一次？ N次;它是O（N）。

您也可以使用其他指令的頻率。我們會看到這並不重要。如果你這樣做，你會得到O（6N + 5），或者類似的東西（因爲沒關係，我會把你的數量計算在內）。

如果你有東西加在一起，只保留最大的一個（當N很大時）。當N很大時，6N> 5，所以你只需保持O（6N）。

丟棄恆定乘數。所以你保留N並得到O（N）。

因爲我們只關心大的N會發生什麼，所以我們放棄了大N最大的一個。對於大的N，小的東西變得微不足道。

我們拋棄了常數乘法器，因爲我們不關心精確的指令數量，而只是：當您將N的大小加倍時，時間會發生什麼變化？當我們三倍，四倍，你有什麼，N的大小，會發生什麼？無論乘以6還是任何其他常數都無關緊要 - 所以我們放棄了不變的乘數。

Answer 2

是，否。它在O(n)中，因爲您重複for循環n次。作業和聲明是O(1) - 不變。我不知道你從哪裏拍了6n + 5。前三行只完成一次。在最壞情況下，循環重複n次，每個數字大於參數。所以你有4*O(1)。由於最後一條語句不在循環之中，因此它只執行一次。總計3 + 4*n + 1 = 4n + 4。占主導地位的是4n，刪除常數，你得到O(n)時間。

通過主導術語的意思，對於n到無窮大，真的沒有，如果你通過2,3,4乘以或其他一些數除以它，這當然適用於一些非常大的數字，因爲沒有無限事與電腦。