如何計算複雜度

Question

我發現我的算法總是會執行n!*4^n步驟。我想知道它的複雜性是O(n!*4^n)還是別的？謝謝。

Answer 1

如果是這樣，正好n!*4^n步驟，沒有真正的需要大哦表示法。

是的，這意味着它具有O(n!*4^n)複雜性。

Answer 2

如果你確信你的算法會做總是n!⋅4ⁿ步驟，這是一個O(n!⋅4ⁿ)，以及它是一個Θ(n!⋅4ⁿ)以及它是一個Ω(n!⋅4ⁿ)。

Answer 3

這是Θ(n!⋅4ⁿ)因爲Θ是下界O它也是O(n!⋅4ⁿ)而且這是Ω(n!⋅4ⁿ)。

重要的是你在做什麼？如果每個步驟都是O（1），這個符號就成立了，但在其他情況下，這取決於你的步驟，我建議向我們展示你的功能，看看有什麼步驟。

爲什麼你不能說它是O(n!)？因爲你不能找到恆c這樣的：

ň⋅4ⁿ≤c⋅n！對於n>ň

因爲對於任何常數c時4ⁿ > c（例如！當n ≥ c）以上的不平等是錯誤的。