java - 次のメソッドの時間計算量

Question

次のメソッドの時間の複雑さを判断しようとしています。最初に、m^3 を生成する 3 つの for ループがあります。メソッドの最後にある再帰呼び出しの時間の複雑さを判断する方法がわかりません。

誰かがこれで私を助けることができますか?

void p(int n, int m) {
    int i,j,k ;
    if (n > 0) {
        for (i=0 ; i < m ; i++)
            for (j=0 ; j < m ; j++)
                for (k=0 ; k < m ; k++)
                    System.out.println(i+j*k) ;  
        p(n/m, m) ;
    }
 }

Answer 1

あなたが言及したように、 O(m^3) は追加の再帰なしの実行です。

合計時間は、この 1 ステップの時間の倍数です。

n = m^(k-1) は k 回実行されるステップであるため、O(k*m^3)、すなわち O(ln(n)*m^3) になります。