算法的大O複雜度

我想弄清楚算法的確切的大O值。我將提供一個例子：算法的大O複雜度

for (int i = 0; i < n; i++) // 2N + 2 
{ 
    for (int x = i; x < n; x++) // N * 2N + 2 ? 
    { 
     sum += i; // N 
    } 
} // Extra N?

所以，如果我打破一些的這個下來，INT I = 0會O（1）中，i < n爲N + 1，I + +是N，乘內環由N：

2N + 2 + N（1 + N + 1 + N）= 2N^2 + 2N + 2N + 2 = 2N^2 + 4N + 2

添加的N爲循環終止和總和常數，= 3N^2 + 5N + 2 ...

基本上，我不是100％確定如何計算確切 O表示法，我的猜測是O（3N^2 + 5N + 2）。

來源

2016-08-25 Awbelton

使用Big-O時，可以省略常量和所有非最高階項。在這種情況下，O（3N^2 + 5N + 2）=> O（n^2）。這是因爲隨着n的增長，這些術語以n^2爲主，變得非常微不足道。 – Clip

你的情況是'N'？「int i = 0將是O（1），」---呃，不。大O分析不是當你在一堆中加入不同的東西時。 – zerkms

邏輯上，'i

你是什麼意思？大O是一個漸近上界，所以它的定義並不確切。

由於O（N + 1）不正確，因此將i=0考慮爲O（1）和i<n。相反，將外部循環看作n次執行，並且對於外部循環的每次迭代，內部循環最多執行n次。循環內的計算需要一定的時間（隨着n變大，計算並不複雜）。所以你最終得到O（n * n * 1）= O（n^2），二次複雜度。

當詢問「確切」時，您將運行內循環，從0到n，然後從1到n，然後從2到n，...，從（n-1）到n，每次做一個恆定的時間操作。所以你做n + (n-1) + (n-2) + ... + 1 = n*(n+1)/2 = n^2/2 + n/2迭代。要從計算的確切數目到大O符號，省略常數和低位術語，最後以O（n^2）結尾（省略了1/2和+n/2和+n/2）。

來源

2016-08-25 03:27:53 user835611

-2

大O意味着最壞情況的複雜性。

而在這種情況下，最壞的情況只有在兩個循環都會運行n個時間，即n * n時纔會發生。

因此，複雜性是O（n2）。

來源

2016-08-26 06:18:29 Durgesh

大O並不一定意味着最壞情況下的複雜性。它是一個普遍的漸近界。您也可以將其應用於預期的運行時或任何其他功能。 – AEF

好友，小o是不緊的界限，大O是最壞的情況，但緊緊地綁定。但是，通常我們不使用小的o來表示最壞情況的複雜度。我們用Big O來說最壞的情況。 – Durgesh

這是不正確的。大O給任意函數提供了一個漸近上界。你可以用它來描述你想要的任何函數的行爲。如果該函數描述「每個輸入長度的最壞情況複雜度」或「每個輸入長度的平均個案複雜度」，甚至「世界上每個人數消耗的全球蘋果量」，則無關緊要。這是一個比你想像的更普遍的概念。 – AEF

算法的大O複雜度

回答

相關問題