关于 while 循环在 for 循环中的时间复杂度的混淆
我正在学习时间复杂度，并且理解它的要点，但有一件事真正让我困惑，那就是理解 for 循环中 while 循环的时间复杂度。
这是我正在分析的代码：
sum := 0
for i := 1 to n
j := 1
while j ≤ i
sum += j
j*=5
end
end
我已经对此进行了尝试，并制作了这个表格，将其分解：
| 代码： | 成本： | # OF TIMES： | 时间复杂度： |
|---|---|---|---|
sum := 0 | 1 | 1 | 1 |
for i := 1 到 n | int i = 1 (1) | 1 | 2n+1 |
| i<=n (1) | n+1 | ||
| i++ (1) | n | ||
j := 1 | 1 | n | n |
当 j ≤ i | j ≤ i (1) | ？ | ？ |
sum += j | 1 | ? | ？ |
j*=5 | 1 | ？ | ？ |
end | 0 | 1 | 0 |
end | 0 | 1 | 0 |
我理解 for 循环的时间复杂度是如何工作的，但是当我到达 while 循环时我很困惑。
我知道赋值的成本为 1，比较的成本为 1。
如果 while 循环写为：
sum:=0
j:=1
while j<=n
sum+=j
j*=5
end
由于它以 5 的增量移动：(j*=5)，其时间复杂度为为：log base5 n。
但是代码中的 while 循环出现了 j<=i，这让我很困惑。
有人可以帮助我计算 while 循环各行的成本/次数，我真的很感激。
仅供参考：这不是学校的作业或类似的东西，我真诚地试图为自己理解这个概念。
I'm learning about time complexity and I understand the gist of it, but there's one thing that's really confusing me, it's about understanding the time complexity of a while loop in a for loop.
This is the code I am analyzing:
sum := 0
for i := 1 to n
j := 1
while j ≤ i
sum += j
j*=5
end
end
I've given a shot at this and I made this table, breaking it down:
| CODE: | COST: | # OF TIMES: | TIME COMPLEXITY: |
|---|---|---|---|
sum := 0 | 1 | 1 | 1 |
for i := 1 to n | int i = 1 (1) | 1 | 2n+1 |
| i<=n (1) | n+1 | ||
| i++ (1) | n | ||
j := 1 | 1 | n | n |
while j ≤ i | j ≤ i (1) | ? | ? |
sum += j | 1 | ? | ? |
j*=5 | 1 | ? | ? |
end | 0 | 1 | 0 |
end | 0 | 1 | 0 |
I understand the how the time complexity works for the for loop, but when I get to the while loop I'm confused.
I know that assignments have cost of 1 and comparisons have a cost of 1.
If the while loop was written as:
sum:=0
j:=1
while j<=n
sum+=j
j*=5
end
Since it's moving in increments of 5: (j*=5), its time complexity would be: log base5 n.
But the while loop in the code goes j<=i, which is throwing me off.
I someone could help me with cost/# of times the individual lines of the while loop, I would really appreciate it.
fyi: this isn't an assignment for school or anything like that, I'm genuinely trying to understand this concept for myself.
If the table above doesn't format correctly, here is a ss of it
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
您的循环相当于从
1到n的所有i的log_5(i)之和。对数底数并不重要，它是一个常数；所以从现在开始我只会说log。该总和渐近等于n log n。这样想：如果您查看log图表，它真的非常平坦，因此您的值中的大部分求和看起来与log函数相同。这只是一个直觉提示，不是正式证明，但已经足够了。如果您需要正式证明，查看这篇文章Your loop is equivalent to the sum of
log_5(i)for allifrom1ton. The logarithm base doesn't matter, it's a constant; so i'll just saylogfrom now on. This summation is asymptotically equal ton log n. Think about it this way: If you look at the graph oflog, it's really, really flat, so most of the higher values in your summation look the same to thelogfunction. This is only an intuition hint, not a formal proof, but it's sufficient. If you need a formal proof, check out this post