简单的循环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,您可以将起始位数log ₂ log 加倍n次.

至于问题的另一个方面,是的,O(一个n的根)可能是某个常数a的有效复杂性类.它更熟悉地写成O(n ^1/a).