如何找到while循環的時間複雜度（大O）？

代碼1如何找到while循環的時間複雜度（大O）？

int i = 0; 
int j = 0; 
while(i < n){ 
    while(j < n){ 
     printf("{%d,%d}",arr[i],arr[j]); 
     j++; 
    } 
    i++; 
    j = 0; 
    printf("\n"); 
}

代碼2

int result = 0; 
int i = 0; 
while (i < n/2){ 
    result += arr[i]; 
    i += 1; 
    while (i >= n/2 && i < n){ 
     result += arr[i]; 
     i += 1; 
    } 
} 
printf("%d\n", result);

我只知道如何找到時間複雜度與循環，但我不確定while循環。如果有人能幫我找到每個代碼的總運行時間，將不勝感激。

來源

2017-06-03 stanley cho

第一個是相當於'爲（I = 0; I melpomene

由於您可以將每個for-loop表示爲while循環，並且您聲明瞭解for循環中的時間複雜性，所以我認爲您擁有解決此任務的所有工具。 – nemo

for循環可以簡單地重寫爲while循環，而大多數while循環可以平凡地重寫爲相應的for循環。請記住，大O符號大約是數量級，而不是確切的數值。 –

第一個代碼示例幾乎是循環的類。它的複雜性是O（n^2）。這是因爲內部循環具有複雜度O（n）並且運行n次。

第二個是比較困難的，直到你看到，它等效於非嵌套循環（忽略的檢查的複雜性）

int result = 0; 
int i = 0; 
while (i < n){ 
    result += arr[i]; 
    i += 1; 
} 
printf("%d\n", result);

意味着它的複雜性爲O（n）

計算時間複雜度的最佳方法是試着真正理解算法的工作原理和計算操作。在第二個例子中，內層循環從不運行直到外層循環處於最後一次迭代。而且，因爲他們甚至執行相同的代碼，整個事情可以減少到一個循環。

另一個很好的例子是這樣的：

for(i=0;i<n;i++){ 
    for(j=i;j<n;i++){ 
     //do something 
    } 
}

讓我們來算的操作：1 + 2 + 3 + 4 + ... + N。這歸結爲n * n/2導致O（n^2）

來源

2017-06-03 20:29:42

A循環，在一天結束時，是一個while循環。形式的東西：

for(int i=0; i<n; i++)

等同於：

int i=0; 

while(i<n) 
{ 
i++; 
}

其實在你應該做任何for循環到你的算法while循環算法純數學分析（有幾個原因）。

回到你的代碼。分析很簡單：

- 在while循環的第一次迭代之前，i的值爲0. - 存在更新變量i（i ++）的唯一語句。 - 在外循環的每次迭代中，我增加1. - 外循環最多運行n次。

-Before任何循環的迭代j的值是0。 - 有2條語句更新Ĵ（J = 0和j ++） -Informally：我們可以在內部循環的值的任何迭代之前告訴j的值爲0. - 在內部循環中，更新j的唯一語句是j ++。 - 內部循環j的每次迭代都會增加1. - 內部循環最多由環保護運行n次。

- 外循環最多運行n次，對於外循環的每次迭代，內循環最多運行n次。所有其他的陳述是不變的。該算法是在O（N * N）= O（N^2）

第二個稍微迴旋但：

-Before外環i的值是0的第一次迭代。（n/2 - 1） - 更新語句（i + = 1）將i更新爲（n/2） - 無規則地：內部循環運行nn/2 = n/2）次，它只運行一次。 - 外循環運行n/2次，內循環運行n/2次恰好一次。

該算法從而運行爲O（n/2 + N/2）= O倍

來源

2017-06-03 21:20:53 Makogan

如何找到while循環的時間複雜度（大O）？

回答

相關問題