for(int i = 1; i <= n; i++)
for (int j = 1; j <= log5(i); j += 3)
这样的循环(主要是第二个循环)的时间复杂度应该怎样推导呢?
1
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))
|
2
tjbwyk 2017-12-12 17:25:43 +08:00 via Android
或者假设第二层循环上限是 log5(n),那原来的时间复杂度<=O(n*log5(n)/3),化简是一样的
|
3
tjbwyk 2017-12-12 17:27:41 +08:00 via Android
已经忘了怎么算了。。比如时间复杂度的下限什么的。。
|