遵循嵌套依赖环的时间复杂性是多少
for(int i = 2; i < N; i ++)
for(int j = 1; j < N; j = j * i)
sum += 1
我得到
我们可以进一步概括吗？
for(int i = 2; i < N; i ++)
for(int j = 1; j < N; j = j * i)
sum += 1
I got
Can we generalize it further?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
使用关于对数的代数身份，logᵢ（n）= log n/log I，因此我们可以将日志n作为一个因素，然后求和为1/log I。将此求和为1/log x的积分近似，我们渐近地认为它是o（n/log n），per Wikipedia 。由于我们以前取出了log n的因素，因此将其乘以O（n）的最终结果。
Using an algebraic identity about logarithms, logᵢ(N) = log N/log i, so we can take log N out as a factor and the summation is then of 1/log i. Approximating this summation as the integral of 1/log x, we get that asymptotically it is O(N/log N), per Wikipedia. Since we previously took out a factor of log N, multiplying by this gives a final result of O(N).