算法複雜度和大O符號

我正在參加一個在線課程的算法，我有以下測驗。我弄錯了，並試圖理解答案的理由。算法複雜度和大O符號

以下哪項是O（n^3）？

一個）的11n + 151 + GN 100
B）1/3 N^2
C）25000 N R個3
d）所有上述的。

正確答案是（d）以上全部。原因在於Big-O符號在n變大時僅提供函數增長率的上限。

我不知道爲什麼答案不是（c）。例如，（b）的上限小於n^3。

2017-04-30 Luca

如果事情是O（n^2），那麼它也爲O（n^3）。 – Lee

上限不一定意味着*最嚴格*限制。 – SomeWittyUsername

沒有「該」的上限。有許多上限。 Big-O符號指定**和**上限。一個相關的符號提供*最小*上限，但它不是大O符號。 –

原因是，正式，大O符號是一個漸近上限。

所以1/3*n^2是O(n^2)，但它也是O(n^3)和O(2^n)。

雖然在日複雜的關於複雜度的轉換中，O(...)被用作嚴格（上下限），但是theta-notation或Θ(...)在技術上是正確的術語。

2017-04-30 17:52:51

回答