显示以下代码片段的 O 表示法
Show the O-notation for the following code fragment
问题是显示以下代码片段的 O 符号（显示每一行）
for x=1 to n
{
y=1
while y < n
y=y+y
}
我相信第一行的 O 表示法是 n。
我不确定 while 循环的 O 表示法是什么，为什么？
给出的答案是O(n log 2n )
有人可以给我解释一下吗？谢谢！
假设 n=64（或 26），则 while 循环将 运行 6 次，y 的最终值为：
2
4个
8个
16
32
64
如果对 n=256（或 28）重复此操作，您会发现有 8 次迭代。用更一般的术语来说，给定 n 值的执行次数将是 log 2n。由于外层循环为n，总执行时间为O(n log 2n )
在内部循环中，y 取值 1、2、4...
y每次乘以2所以它的形式是2^k
此循环在最大值 k 处停止，例如 2^k < n 即 k < log_2(n)
这个循环不会超过log_2(n)次迭代
x取值范围为1到n，可能总迭代次数增加n。log_2(n)
问题是显示以下代码片段的 O 符号（显示每一行）
for x=1 to n
{
y=1
while y < n
y=y+y
}
我相信第一行的 O 表示法是 n。 我不确定 while 循环的 O 表示法是什么，为什么？
给出的答案是O(n log 2n )
有人可以给我解释一下吗？谢谢！
假设 n=64（或 26），则 while 循环将 运行 6 次，y 的最终值为：
2 4个 8个 16 32 64
如果对 n=256（或 28）重复此操作，您会发现有 8 次迭代。用更一般的术语来说，给定 n 值的执行次数将是 log 2n。由于外层循环为n，总执行时间为O(n log 2n )
在内部循环中，y 取值 1、2、4...
y每次乘以2所以它的形式是2^k
此循环在最大值 k 处停止，例如 2^k < n 即 k < log_2(n)
这个循环不会超过log_2(n)次迭代
x取值范围为1到n，可能总迭代次数增加n。log_2(n)