我對這個特定問題有疑問，答案是說 big-Oh(n^2) 演算法不會比 big-Oh(n^3) 演算法運行得更快，而如果兩種情況下的符號都是 theta，那么它就會有是真的，但為什么會這樣？
如果有人能詳細地向我解釋，我會很高興的，因為我找不到任何可以澄清我的疑問的來源。
uj5u.com熱心網友回復：
第 1 部分已釋義（請注意，問題中的措辭在“數字”被量化的情況下是模棱兩可的——必須在您選擇兩種演算法后選擇它，但我認為這就是預期的目的）。
給定函式 f 和 g，其中 f=Theta(n^2) 和 g=Theta(n^3)，那么存在一個數 N，使得對于所有 n>N，f(n) < g(n)。
第 2 部分釋義：
給定函式 f 和 g，其中 f=O(n^2) 和 g=O(n^3)，那么對于所有 n，f(n) < g(n)。
1 是真的，你可以通過應用 big-Theta 的定義來證明它。
2 是錯誤的（作為一般陳述），您可以通過找到 f 和 g 的單個示例來反駁它。例如，f(n) = 2，g(n) = 1。Big O 是一種上限，所以這些常數函式起作用。題中給出的反例是f(n)=n, g(n)=log(n)，但原理相同。
uj5u.com熱心網友回復：
答案說 big-Oh(n^2) 演算法不會比 big-Oh(n^3) 演算法運行得更快
更微妙的是：O(??2) 演算法可能比 O(??3) 演算法運行得慢。這不是意愿，而是可以。
答案給出了一個原因，但實際上有兩個：
大 O 符號只給出一個上限。引自維基百科：
用大 O 符號描述函式通常只提供函式增長率的上限。
所以任何 O(??) 也是 O(??2) 和 O(??3)，但不一定反之亦然。答案是 O(??3) 的演算法可能有一個更嚴格的界限，即 O(log??)。的確，這聽起來可能很愚蠢，因為當它也是 O(log??) 時，為什么要說它是 O(??3)？那么只談 O(log??) 似乎更合理。而這也是我們經常做的。但還有第二個原因：
第二個選項在其宣告中沒有約束“n > number”。這是必不可少的，因為無論時間復雜度如何，對于給定的 ?? 值的演算法的運行時間都無法根據其時間復雜度來確定。O(??log??) 的演算法可能需要 10 秒才能完成它的作業，而 O(??2) 的演算法可能需要 8 秒才能得到相同的結果，即使它的時間復雜度更糟。在比較時間復雜度時，您只能獲得有關漸近行為的資訊，即當 ?? 大于足夠大的數字時。
因為這個額外的約束是第一個宣告的一部分，所以它確實是真的。
轉載請註明出處，本文鏈接：https://www.uj5u.com/gongcheng/387587.html