找到最大的O-O

Question

我在學習並理解如何找到最緊密的O O符號。在這裏，我需要爲這些算法找到最緊密的大O符號，並且我計算了運行時間。

現在我需要證明或找到最嚴格的大O符號，但我不知道我應該從哪裏開始。

1）2 n^2+ 2 n +2= O(n^2)

2）6 n log n +4n +2 =O (n log n)

3）6 X1000 n+ 4n +2 = O(n)

不能確定如何解決這部分被從提問。我如何確保我的方程式最緊張？

任何幫助或建議將不勝感激，謝謝！

Answer 1

簡單地說：你採取一個「最高」的術語，並刪除所有恆定的乘數。

這背後的原因是，隨着n增長，最高期限將佔總時間最多。所以休息會變得微不足道，足夠大n。去除恆定的乘數就是時間複雜度的定義。