兩次通過數組爲O（n）或O（2N）

我是在採訪蛋糕練的一些問題，以及問題2給出的解決方案採用兩個獨立的迴路（未嵌套）和解決方案供應商聲稱，他/她在O（n）時間解決了它。根據我的理解，這將是O（2n）次。我的想法是錯誤的，還是解決方案提供商犯了錯誤？從採訪蛋糕兩次通過數組爲O（n）或O（2N）

摘錄：

2016-03-08 Hossam

O（n）== O（2n）== O（kn）。常量不重要，只有比例因子。 – azurefrog

O（2n）攤銷到O（n），因爲與「n」相比，因素「2」具有不成比例的小影響（在最壞的情況下） –

完美，謝謝！ – Hossam

大O符號爲您提供關於如何做你的算法執行時間取決於輸入數據的提示。當你看到那個時間複雜度爲O（n）的你明白，有輸入和執行時間之間的線性依賴。常量沒有提及。

根據定義＆奧米克;（G（N））是每個的所述下面的語句保持組函數：存在這樣的正的常數Ç和Ñ該0 ≤F（N）≤CG（n）的適用於所有ñ≥ñ。你看定義是使用任意常數Ç，如果你的克（N）本身具有恆定的，不會有任何區別。

最終，我們有：O（CG（n））的 = O（G（N））。在特定情況下O（CN） = O（2N） = 爲O（n）。它們都代表相同的一組功能。

2016-03-08 20:44:48

那麼，如果面試官在採訪中要求開發一個在O（n）時間運行的算法，並且我在O（2n）時間內寫一個算法，那麼這不應該是一個主要問題？ – Hossam

@Hossam，它只是**冗餘**說* O（2n）*，因爲它與* O（n）*相同。我不認爲這會影響你的採訪結果:)。 –

大O符號是最有用的，看看如何代碼規模。也就是說，如果我將數組的大小加倍，代碼需要多長時間才能運行？如果您的代碼是O(n)，則需要兩倍的時間，而如果是O(n^2)，則需要4倍的時間，以此類推。在這種情況下，無論您是否通過循環兩次，將數組的大小加倍會比以前長兩倍（每個循環的長度是兩倍）。

2016-03-08 20:35:14

回答