時間の複雑さを計算するには？

Question

私は、時間の複雑さを計算するためのいくつかの基本的な概念を説明しました。私はそれに続くコードの複雑さを知りたい。

時間の複雑さはO（ログn * n ）と思われます。それはまだ間違っているかもしれないし、私は正確な答えと同じように到着する方法を知りたい。ありがとう:) N回の反復で

function(int n){ 
    if(n == 1) return; 
    for(int i = 1; i <= n; i++) 
     for(int j = 1; j <= n; j++) 
      printf("*"); 
    function(n-3); 
    } 

Answer 1

二つのネストされたループはにはO（n^2）を与えます。再帰は、O（n）の関数自体を呼び出します。これは、定数が3の場合にnになるため、n/3 + 1 = O（n）となります。合計で、それはO（n^3）です。

結果の対数定数は、n/3という値で関数が呼び出された場合に発生します。