Big-O和通用時間單位？

我有這兩個問題，我想我明白如何回答（問題後的答案）。我只想看看我是否理解時間複雜度計算以及如何找到BigO。
通用形式只是表達式右側每個值的乘積。
BigO是多項式中最大的力量。這種想法是正確的嗎？Big-O和通用時間單位？

int sum = 0; 
for (int i = 0; i < n; i++) 
    for (int j = 0; j < n * n; j++) 
     for (int k = 0; k < 10; k++) 
     sum += i;

多少普通時間單位這段代碼走？ n（n^2）* 10 這段代碼的大運行時間是多少？ O（n^3）

2012-04-30 LF4

是的。基本上，大O定義你的時間單位（如你稱之爲）的時間單位是從一個恆定的時間開始，從某個（任意高的）自然數開始到無限大。如果存在一個常數C和一個數N，那麼函數f（n）就是O（g（n）），這樣f（n）代表C（g）所有n> N。

在你的上下文f（n）= n（n^2）* 10和g（n）= n^3。

順便說一句，你也可以說這個函數是O（n^4）。您可以使用big theta符號來表示這也是下界：f（n）是$ \ theta（n^3）。

2012-04-30 05:54:44 smichak

是的你的理解是正確的。但有時你也必須處理對數項。查看對數項的方法可以將其視爲n ^（1 + epsilon）。 epsilon的數量很小。

2012-04-30 05:47:36 Apurv

有趣的我想知道，如果它是對數我不明白這是很好。 – LF4

@ LF4：好吧，這裏是一個天真的解釋。你知道log（n）在O（n）和O（n^2）之間。我們這樣做的方式是把log（n）表示爲n ^（1 + e），其中e是非常小的數量。這解釋了一切。 – Apurv

回答