函數的大O計算

我需要知道這個函數的O. （和每個環）

int find_c(int n) 
    int i,j,c 
    for(i=n*n; i > 1; i=i/4) //O(logn) 
    for(j=n*n; j > n/2; j--) //? 
     c++ 
    for(i=c; i > 0; i--) //O(c) 
    if(random(0...99) > 0) //O(1) 
     for(j=n; j > 0; j--) //O(n) 
     c++ //O(1) 
    else 
     for(j=400; j > 1; j--) //O(400)? 
     c++ //O(1) 
    return c

來源

2016-09-25 user3743266

你有沒有嘗試過，甚至對自己這樣做呢？如果是這樣，至少發表一些你的想法或部分解決方案。例如'C++'顯然是'O（1）'。對「隨機（0 ... 99）」的執行可能也是如此。 – rbaleksandar

我自己試過這個，但我不知道我的答案是否正確。是否全部if/else部分O（1）* inner-O？ – user3743266

'if'和'else'本身並沒有思考。它在'if'中的邏輯表達式很重要。如果你有'if（a == 2）'或類似的，你有'O（1）'，但是如果你比較了那個'if'裏面的字符串等等。 – rbaleksandar

int find_c(int n) 
    int i,j,c 
    for(i=n*n; i > 1; i=i/4) //O(logn) 
    for(j=n*n; j > n/2; j--) //O(n2) 
     c++ //c = O(n2.logn) 
    for(i=c; i > 0; i--) //O(n2.logn) 
    if(random(0...99) > 0) //O(1) 
     for(j=n; j > 0; j--) //O(n) 
     c++ //O(1) //c = O(n3logn) 
    else 
     for(j=400; j > 1; j--) //O(1) 
     c++ //c = O(n2log2) 
    return c

所以最終的答案是O（n^3.log N）

來源

2016-09-25 17:09:39 galinette

在第一個循環中，c值= O（logn * n^2）？後來你使用c值，每當它循環c次咋？ – user3743266

是的，這是在評論 – galinette

函數的大O計算

回答

相關問題