我試圖了解在PC上運行程序的背景下Big O分析的特定方面。假設我有一個性能為O（n + 2）的算法。在這里，如果n真的很大，則2變得無關緊要。在這種情況下，很明顯，實際性能為O（n）。但是，可以說另一種算法的平均性能為O（n ^ 2/2）。在我看到該示例的書中，實際表現為O（n ^ 2）。我不確定為什么，我的意思是在這種情況下2似乎并不完全無關緊要。因此，我一直在從書中尋找清晰的解釋。這本書是這樣解釋的：“雖然要考慮1/2的含義。檢查每個值的實際時間高度取決于代碼轉換成的機器指令，然后取決于CPU執行指令的速度。因此1/2并不正確。不是很重要?！蔽业姆磻恰?？我從字面上不知道所說的是什么，或更確切地說，該陳述與他們的結論有什么關系。有人可以幫我拼一下嗎。謝謝你的幫助。
3 回答
慕神8447489
TA貢獻1780條經驗 獲得超1個贊
“這些常量有意義還是相關？”之間有區別。和“大O表示法是否關心它們？” 第二個問題的答案為“否”，而第一個問題的答案為“絕對！”。
Big-O表示法并不關心常量，因為big-O表示法僅描述函數的長期增長率，而不是函數的絕對值。將一個函數乘以一個常數只會對其常數的增長率產生影響，因此線性函數仍會線性增長，對數函數仍將對數增長，指數函數仍呈指數增長，等等。由于這些類別不受常數的影響，因此不會無論我們刪除常數。
也就是說，這些常量絕對重要！的函數，其運行時間為10 100 n將被方式比其運行時只是N A功能慢。運行時間為n 2/2的函數將比運行時間僅為n 2的函數快。前兩個函數均為O（n）且后兩個函數均為O（n 2）的事實并沒有改變它們不在相同時間段內運行的事實，因為這不是big-O表示法專為。O標記法對于確定一個功能在長期內是否會大于另一個功能非常有用。盡管10 100對于任何n> 0，n都是一個巨大的值，該函數為O（n），因此對于足夠大的n最終，它將擊敗運行時間為n 2/2的函數，因為該函數為O（n 2）。
綜上所述-由于big-O僅談論增長率的相對類別，因此它忽略了恒定因素。但是，這些常數絕對重要。它們只是與漸進分析無關。
希望這可以幫助！
添加回答
舉報
0/150
提交
取消