while循環的大O

我前幾天有過這個問題，但我仍然不確定自己是否正確。while循環的大O

for(int i =1; i <n; i++) //n is some size 
{    
    for(j=1; j<i; j++) 
    { 
     int k=1; 

     while (k<n) 
     { 
      k=k+C; //where C is a constant and >=2 
     } 
    } 
}

我知道嵌套的for循環是O（n^2），但我不知道用while循環。我認爲整個代碼將是O（n^3）。

來源

2011-10-03 user977151

你的意思是我 DeCaf

@DeCaf我認爲這是一個錯字 –

請修正問題中的拼寫錯誤，並將其格式保持一致。 – 2011-10-03 17:59:47

int k=1; 

    while (k<n){ 
     k=k+C     //where C is a constant and >=2 
    }

這將花費(n-1)/C步驟：寫u =（k-1）/ C。然後，K =銅+ 1和表正式

u=0; 
while(u < (n-1)/C) { 
    u=u+1 
}

因此，while循環O(n)（因爲C是常數）

編輯：讓我嘗試解釋周圍用另一種方式。

從虛擬變量u開始。迴路

u=0; 
while(u < MAX) { 
    u = u+1 
}

運行MAX次。

當你讓MAX = (n-1)/C，環路是

u=0; 
while(u < (n-1)/C) { 
    u=u+1 
}

而且運行(n-1)/C倍。現在

，檢查u < (n-1)/C相當於C*u < n-1或C*u + 1 < n，所以循環相當於

u=0; 
while(C*u + 1 < n) { 
    u=u+1 
}

現在，假設我們在一個變量k = C * u + 1條款改寫了這個循環。然後，

u=0; 
k=1; // C * 0 + 1 = 1

循環看起來像

while(C*u + 1 < n) { 
while(k < n) {

和內部條件是

u=u+1 
    k=k+C //C * (u+1) + 1 = C * u + 1 + C = old_k + C

全部放在一起：

int k=1; 

    while (k<n){ 
     k=k+C 
    }

採取(n-1)/C步驟。

來源

2011-10-03 17:57:32

我很困惑，爲什麼你有「你」。你能詳細解釋一下嗎？ – user977151

@ user977151最簡單的事情就是一次一步走一步。我想重做反向 –

內環是字面上O(n/C)=O(n)，所以是的，總的來說這是O(n^3)（第二循環有一個上限的O(n)）

來源

2011-10-03 17:58:29 Blindy

感謝分析您的回覆:) – user977151

那麼，你就需要看，而循環體有多少次運行給定的n和C值。例如n是10，C是3.身體將運行3次：k = 1，k = 4，k = 7。對於n = 100和C = 2，身體將運行50次：k = 1,3,5,7,9，...，91,93,95,97,99。這是由C計算直到n的問題。你應該能夠從這個線索中計算出Big-O的複雜性。

來源

2011-10-03 18:02:12

我不喜歡你的計數方法無窮序列（這是BTW漸進方式）......一個簡單的「循環的數量呈線性'N'在增長1/2「的比率更容易理解並且更加準確。 – Blindy

形式上，您可以繼續使用以下方法（西格瑪符號）：

enter image description here

哪裏a如果要統計的準確數字象徵着不斷操作的最內層循環內（a = 1數迭代）。

來源

2014-03-31 15:20:39

傷心imgur.com被我的公司代理完全阻止：| –

你能[解釋LaTeX代碼]（http://www.codecogs.com/latex/eqneditor.php）嗎？我可以和你分享劇本。 –

無法從SO關於它的atm找到報價。我個人認爲它會很酷（而且Latex甚至可以被索引，但是我不確定其他人是否會讚賞它，因爲它可能會混淆您發佈的讀者，具體取決於您如何添加它，所以我要在家裏看。 [也許有人應該問這樣整合某種乳膠到html渲染器（http://stackoverflow.com/questions/116054/what-is-the-best-way-to-embed-latex-in-a-webpage） ] –

while循環的大O

回答

相關問題