奇怪循环的时间复杂度
Time Complexity of a weird loop
这个循环的时间复杂度是多少？
for(int i = 0; i < n*n; i *= 2)
{ //Something with O(1) complexity here }
我猜 O(log n*n)。
你是对的，因为 i 在每次迭代中加倍，当 i >= n2 时循环终止，运行 O(log n2) 次迭代。
但是，请注意 O(log n2) = O(2 log n) = O(log n).
编辑：但是，正如 Zilog80 指出的那样，这段代码将 i 初始化为 0，这将导致循环 运行 无限因为 0 * 2 = 0。但是，如果您将其初始化为某个正数（常数），那么您的计算是正确的。
这个循环的时间复杂度是多少？
for(int i = 0; i < n*n; i *= 2)
{ //Something with O(1) complexity here }
我猜 O(log n*n)。
你是对的，因为 i 在每次迭代中加倍，当 i >= n2 时循环终止，运行 O(log n2) 次迭代。
但是，请注意 O(log n2) = O(2 log n) = O(log n).
编辑：但是，正如 Zilog80 指出的那样，这段代码将 i 初始化为 0，这将导致循环 运行 无限因为 0 * 2 = 0。但是，如果您将其初始化为某个正数（常数），那么您的计算是正确的。