大O時間複雜度

Question

我有一個時間複雜度T（n）= 6n + xn，顯然大O複雜度是（n^2），但我認爲它會是（n）。我想了解它爲什麼是（n^2）。

Answer 1

T（N）= O（G（N））中的計算機科學指本

所以明顯的T（n）的函數在集合O屬於（N^2）

但主要問題是，你在T（n）中的'x'是否依賴於n的輸入？

如果答案是肯定的，那麼很明顯，T（N）= O（N）+ XN屬於集合爲O（n^2）

如果答案是否定的，並且x是隻是一個常數因子，以及那麼T（n）當然屬於也是 O（n^2）（鬆散的上限）。但是更緊的上界是T（n）屬於O（n），因爲T（n）= O（n）+ O（n）因爲我們正在談論上限大O符號），說O（n）函數也屬於集合O（n^2）是正確的。如果我們只關心我們的算法甚至在最壞情況下在O（n^2）時間執行。

希望這會有所幫助