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

This topic created in 3165 days ago, the information mentioned may be changed or developed.

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

5 replies • 2017-12-12 17:33:56 +08:00

tjbwyk

Dec 12, 2017 via Android

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

tjbwyk

Dec 12, 2017 via Android

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

tjbwyk

Dec 12, 2017 via Android

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

regicide

Dec 12, 2017

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

tjbwyk

Dec 12, 2017 via Android

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