2016-09-25 7 views
0

関数のOの計算方法は?関数のBig 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 
+1

は、あなたも自分でこれをやってみましたO(N^3.log n)が最終的な答えはありますか?もしそうならあなたの意見や部分的な解決策を投稿してください。例えば、 'C++'は明らかに 'O(1)'です。おそらく 'random(0 ... 99)'の実行に関して同じことが言えるでしょう。 – rbaleksandar

+0

私はこれを自分で試しましたが、答えが正しいかどうかはわかりません。すべてがif/elseの部分ですO(1)* inner-O? – user3743266

+1

'if'と' else'自体には考えがありません。 'if'の中の論理式は重要です。 'if(a == 2)'やそれに類するものがあれば、 'O(1)'を持つことになります。最初のforループの – rbaleksandar

答えて

1
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 

+0

は、c value = O(logn * n^2)ですか?そして、後でそのc値をc回繰り返すたびにその値を使用しますか? – user3743266

+0

はい、これはコメントです – galinette

関連する問題