有一个计算时间复杂度的算法问题需要请教一下 V 友们

[regicide]

for(int i = 1; i <= n; i++)
    for (int j = 1; j <= log5(i); j += 3)
这样的循环(主要是第二个循环)的时间复杂度应该怎样推导呢？

[tjbwyk]

大致如此？ O((log5(n!)/3))=O(log5(n!))<=O(log5(n^n))=O(n log5(n))=O(n log(n))

[tjbwyk]

或者假设第二层循环上限是 log5(n)，那原来的时间复杂度<=O(n*log5(n)/3)，化简是一样的

[tjbwyk]

已经忘了怎么算了。。比如时间复杂度的下限什么的。。

[regicide]

@tjbwyk 就是有点纠结 log5(n)这个点 感谢 看来我还得回去仔细看看书

[tjbwyk]

@regicide 是 log5->log 么？换底之后可以提一个常数项出来