以下代码的时间复杂度是多少？

Question

For(I=1 ; I<=n ; I++)
{
    For(J=1 ; J<=I ; J++)
        {
             For(K=1 ; K<=n^5 ; K=15 × K)
                 {
                      x=y+z;
                 }
        }  
}

根据我似乎是O(N ^ 2 log N),但是当我分析k循环时,它没有跟随Log N,这让我感到困惑,

Answer 1

这应该是O(n^2 log(n))因为内部循环将被调用(n/2)(n+1)次数并且它将循环n^5 = 5 * log base 15n的基数15,因为k在循环数中呈指数增长.

这导致5(n^2+n)(log base 15 of n)/2分配给x,即O(n^2 * log(n))