java - 以下方法的时间复杂度

Question

我正在尝试确定以下方法的时间复杂度。一开始我有三个 for 循环，它们会产生 m^3。我不知道如何确定，方法结束时递归调用的时间复杂度是多少。

有人可以帮我弄这个吗？

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) 是在没有额外回避的情况下执行的。

总时间只是这一步的时间的乘积。

对于 n = m^(k-1) 是执行 k 次的步骤，因此它有 O(k*m^3)，即 O(ln(n)*m^3)。

Answer 2

遵循以下步骤将允许您以正式的方式推断时间复杂度：