big-o - 简单的while循环Big-O复杂性

Question

int a = 3;

while (a <= n) {
    a = a * a;
}

我的版本是它的复杂性是: http://www.mmoprophet.com/stuff/big-o.jpg
有这样的事吗？

Answer 1

那是不对的。 a不能是big-O公式的一部分，因为它只是一个临时变量。

烦恼的是，如果我们将乘法视为恒定时间运算，则执行的乘法次数将为O(log log n)。如果您每次迭代都乘以一个常数，那么它将是O(log n)。因为每次迭代都乘以一个越来越多的数字，所以会有另一个日志。

可以将其视为每次迭代加倍的位数。在超出限制之前，您可以将位数翻倍多少次？位数是log n，并且可以将起始位数log2 log n翻倍。

至于问题的另一个方面，是的，对于某个常数a，O(n的第a个根)可能是有效的复杂度类。它会更熟悉地写为O(n1/a)。