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)。