在渐近分析中添加对数
我正在尝试解决一个问题，非常感谢您的帮助！时间复杂度是多少...
for (int j = 1 to n) {
k = j;
while (k < n) {
sum += a[k] * b[k];
k += log n;
}
}
外部 for 循环运行 n 次。我不确定如何处理内部循环中的 k+= log n 。我的想法是 O(n^2)。将 log(n) 添加到 k 并不能完全获得额外的 n 个循环，但我认为它小于 O(n*log n) 。显然，这只是一个猜测，任何帮助弄清楚如何以数学方式证明这一点的帮助将不胜感激！
Have a problem I'm trying to work through and would very much appreciate some assistance! What's the time complexity of...
for (int j = 1 to n) {
k = j;
while (k < n) {
sum += a[k] * b[k];
k += log n;
}
}
The outer for loop runs n times. I'm not sure how to deal with k+= log n in the inner loop. My thought is that it's O(n^2). Adding log(n) to k isn't quite getting an additional n loops, but I think it is less than O(n*log n) would be. Obviously, that's just a guess, and any help in figuring out how to show that mathematically would be greatly appreciated!
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
您可以将
log(n)视为此处的常量。循环的每次迭代将执行恒定量的工作 (
sum+=...; k+=...)，次数等于n/日志（n）。循环有n次迭代。因此总工作量为n^2 / log(n)。任何时候你看到一堆像这样的操作：
它是
a*b * O(blah)——想象一下正方形（我放置.的地方）。它是 2D 矩形（矩形的一半）的常数部分，因此O(a*b)。在上述情况下，b=
n、a=n/log(n)和 O(blah)=O(1)(从内循环）You can treat
log(n)as a constant here, sort of.Each iteration of the loop will perform a constant amount of work (
sum+=...; k+=...) a number of times equal ton/log(n). There areniterations of the loop. The total work is thusn^2 / log(n).Any time you see a bunch of operations like so:
It is
a*b * O(blah)-- just imagine the square (where I put the.s). It is a constant fraction of a 2D rectangle (half of a rectangle), hence theO(a*b).In the above case, b=
n, a=n/log(n), and O(blah)=O(1)(from the inner loop)您可以很容易地“总结一下”：
外部循环有您所说的
n步骤。内部循环有(kj) / log n步骤。（大致）：
所以，总共是
O((n^2)/log(n))。You can quite easily "just sump up":
The outer loop has as you said
nsteps. The inner loop has(k-j) / log nsteps.That's (roughly):
So, it's
O((n^2)/log(n))in total.您可以按照以下方式正式进行：
You can proceed formally like the following: