大哦表示法運行時間

你如何解決這個問題？你首先得到c是兩個函數的比率，然後用比率找出n的範圍？你怎麼知道？請解釋我真的迷失了，謝謝。大哦表示法運行時間

實施例1：證明運行時間T（N）= N^3 + 20N + 1爲O（n^3）證明：由大哦定義，

T（n）的是O （n^3）如果對於某些n≥n0，T（n）≤c·n^3。

讓我們檢查此條件：

如果n^3 + 20N + 1個≤Ç·N^3然後1 + 20/N^2 + 1/N^3 < = C。

因此， Big-Oh條件適用於n≥n0= 1且c≥22（= 1 + 20 + 1）。較大的 n0的值會導致較小的因子c（例如，對於n0 = 10 c≥1.201等等），但在的任何情況下，上述說明均有效。

2014-01-10 user3076196

請注意，Big-O符號實際上並不告訴你任何事情的運行時間*。它告訴你如何處理的項目數量增加時，某個*的運行時間如何增長。我的意思是說，使用某種算法的Big-O符號不會以任何方式告訴你算法處理* x *元素需要多少秒/時間單位。就Big-O符號而言，你只保留表達式中最大/最大的部分，這就是爲什麼Big-O表示符號'n^3 + 2n^2'是'O（n^3） '。 –

我認爲你所看到的技巧是你沒有考慮大數字。因此，讓我們一反例：

T(n) = n^4 + n

，讓我們假設，我們認爲這是O(N^3)而不是O(N^4)。什麼，你可以看到的是

c = n + 1/n^2

這意味着c，恆定的，實際上是c(n)，取決於n功能。以N來一個非常大的數字表明，無論如何，c == c(n)，功能n，所以它不能是O(N^3)。

你想要的是在極限N趨於無窮，一切，但恆定的遺體：

c = 1 + 1/n^3

現在你可以很容易地說，它仍然是c(n)！由於N得到真的，真的很大1/n^3去零。因此，如果在O(N^4)時間內宣佈T(n)的情況下，非常大的N，c == 1或它是一個常數！

這有幫助嗎？

來源

2014-01-10 21:37:15 wheaties

謝謝小麥！真的很感謝幫助 – user3076196

大哦表示法運行時間

回答

相關問題