時間複雜度 - 計算算法的最壞情況

我正在閱讀一些關於時間複雜度的信息，我很困惑如何實現以下時間複雜性，以及是否有一套特定的規則或方法來解決這個問題？時間複雜度 - 計算算法的最壞情況

1）

Input: int n 
for(int i = 0; i < n; i++){ 
    print("Hello World, "); 
} 
for(int j = n; j > 0; j--){ 
    print("Hello World"); 
}

緊：6N + 5
大O：O（N）

2）

Input: l = array of comparable items 
Output: l = array of sorted items 
Sort: 
for(int i = 0; i < l.length; i++){ 
    for(int j = 0; j < l.length; j++){ 
     if(l{i} > l{j}){ 
} } 
    Swap(l{i},l{j}); 
} 
return ls;

最壞情況時間複雜度：4N2 + 3N + 2 = O（N 2）

來源

2013-04-29 mino

在第一示例中，所述陣列具有n個元素，並且你經過這些元件的兩倍。第一次從索引0開始到i，第二次從索引n開始到0。所以，爲了簡化這個，我們可以說它花了你2n。當與大O符號打交道時，你應該記住，我們關心的範圍：

結果，O（2N）= O（n）的和O（一+ B）= O（n）的

Input: int n      // operation 1 
    for(int i = 0; i < n; i++){ // operation 2 
    print("Hello World, ");  // Operation 3 
    } 
for(int j = n; j > 0; j--)  // Operation 4 
    { 
    print("Hello World");  //Operation 5 
    }

正如您所看到的，我們在循環之外總共有5次操作。

在第一個循環內部，我們執行三個內部操作：檢查i是否小於n，打印「Hello World」，然後遞增i。

在第二個循環內部，我們也有三個內部操作。因此，我們需要的操作總數是：3n（對於第一個循環）+ 3n（第二個循環）+5（循環外的操作）。因此，所需的步驟總數是6n + 5（這就是你的嚴格限制）。

正如我之前提到的，O（an + b）= n，因爲一旦算法是線性的，當n非常大時，a和b沒有太大的影響。

所以，你的時間複雜度將變成：O（6n + 5）= O（n）。

對於第二個示例，可以使用相同的邏輯，因爲兩個嵌套循環取n而不是n。

來源

2013-04-29 13:26:54 John

等待，不打印（「Hello World」）;在循環之外？ – mino 2013-04-29 14:31:56

不，它是在你的代碼中顯示的內部循環（對不起，我無意中添加了一個'{'）。我剛修好了。 – John 2013-04-29 23:50:53

如果它在裏面，那麼爲什麼它包含在OUTSIDE的計算中，即：操作3。 – mino 2013-04-30 20:25:36

對於一個給定的算法，時間複雜度或Big O是一種能夠提供一些很公平「由算法進行總基本操作」的估計與給定的輸入大小n關係。

1型

比方說你有一個這樣的算法中：

a=n+1; 
b=a*n;

有在上面的代碼2個基本操作，不管你n有多大，對於以上因爲算法不依賴於輸入的大小，所以上面代碼的Big-O是O（1）。

2型

對於此代碼：

for(int i = 0; i < n; i++){ 
    a=a+i; 
}

我希望你明白的大O在O（N），作爲基本操作數直接取決於n

大小

3型

現在什麼ABO使用此代碼：

//Loop-1 
for(int i = 0; i < n; i++){ 
    print("Hello World, "); 
} 
//Loop-2 
for(int i = 0; i < n; i++){ 
    for(int j = 0; j < n; j++) { 
     x=x+j; 
    } 
}

正如您所看到的，loop-1是O（n），loop-2是O（n^2）。所以感覺總複雜度應該是O（n）+ O（n^2）。但是沒有，上面代碼的時間複雜度是O（n^2）。爲什麼？因爲我們試圖知道對於給定輸入大小n，由算法執行的基本操作的計數足夠公平，這將會被另一個人比較容易理解。用這個邏輯，O（n）+ O（n^2）變成O（n^2），或者O（n^2）+ O（n^3）+ O（n^4）變成O（n^4））！

同樣，你可能會問：但是怎麼樣？當我們將Big-O的所有較低能力變得如此微不足道時，我們將其與Big-O的較高能力相加，當我們將算法的複雜性描述給另一個人時，我們可以完全忽略它們（較低的能力）？我會嘗試顯示這種情況的原因：O（n）+ O（n^2）= O（n^2）。假設n = 1000，那麼O（n）的確切計數是1000次操作，O（n^2）的確切計數是1000 * 1000 = 1000000，所以O（n^2）是1000倍比O（n），這意味着你的程序將花費O（n^2）的大部分執行時間，因此不值得一提的是你的算法也有一些O（n）。

PS。請原諒我的英語:)

來源

2013-04-29 14:03:04 sowrov

時間複雜度 - 計算算法的最壞情況

回答

相關問題