大O - 增長的函數的速度

Question

我想知道更多關於大O，發現這條信息：

「如果f(x) = O(g(x))的f(x)的增長速度是漸近小於或等於增長率爲g(x)'

在這種情況下漸近是什麼意思？ 另外我有一些困難，理解爲什麼Big-Theta不依賴於我們使用的計算機？ 任何人都可以提供一些關於這兩個問題的更多信息嗎？

Answer 1

在這種情況下，術語「漸近」指的是「當x走向無窮大」。當有人說「f（x）漸近地比g（x）增長」時，「它們意味着對於非常大的x值，函數g（x）將比函數f（x）增長得更快。這意味着對於足夠大的x，只要f（x）和g（x）都是g（x）的值總是最終大於函數f（x）。

對於這個問題：

我也有一定的難度理解爲什麼沒有大-θ取決於我們使用的電腦上？

雖然O，Θ和Ω符號在CS廣泛用來描述運行時間，這實際上是不是他們的意思。從技術上講，這個表示法用來量化函數的增長率，而不管這些函數實際上是什麼意思。例如，你會在離散數學中發現Stirling's approximation中使用的big-O符號，估計ln n！作爲n ln n - n + O（log n），其中O（log n）表示「某種函數的增長率爲O（log n）」。在CS中，當我們說算法是O（n）時，真正意義的是「描述此函數的運行時間的函數是O（n）」。更恰當地說，你會看到諸如「算法的運行時間是O（n）」或「算法花費時間O（n）」等表達式，強調大O符號用於描述算法的運行時間比算法本身。從這個意義上說，對於「爲什麼Θ表示法不依賴於計算機？」這個問題有一個答案。是「Θ符號只是量化功能的增長率，並與電腦無關。」

在另一種意義上，爲什麼特定的計算機沒有關係的原因是Θ符號談論漸近運行時，不絕對運行時間。如果算法的運行時間爲Θ（n），則表示該算法的運行時間縮放爲某些線性函數。該算法的運行時間作爲輸入的大小實際上可能是100n + 137或20,000,000n-15之類的東西，因爲重要的是這些運行時增長的方式，而不是運行時本身。如果您在不同的計算機上運行相同的代碼，則可能需要更多或更少的時間才能運行，具體取決於所選的計算機，但幾乎可以肯定，它不會從線性縮放到按比例縮放。這意味着漸近，運行時間是相同的，儘管絕對運行時可能會非常不同。

希望這會有所幫助！