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

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

已注册用户请登录

这是一个创建于 2345 天前的主题，其中的信息可能已经有所发展或是发生改变。

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

5 条回复 • 2017-12-12 17:33:56 +08:00

tjbwyk

2017-12-12 17:23:21 +08:00 via Android

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

tjbwyk

2017-12-12 17:25:43 +08:00 via Android

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

tjbwyk

2017-12-12 17:27:41 +08:00 via Android

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

regicide

2017-12-12 17:30:21 +08:00

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

tjbwyk

2017-12-12 17:33:56 +08:00 via Android

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