简单的 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，您可以将起始数字加倍 log₂ log n 次。

---

至于问题的另一方面，是的，O(a-n的根)可能是某些常量a的有效复杂性类>。更常见的写法是 O(n^1/a)。

Answer 2

好吧，你实际上可以进入无限循环！

假设 32 位整数：

试试这个：

int a = 3 ;
int n = 2099150850;
while (a <= n)
{
    a = a*a;
}

但是假设没有整数溢出，其他海报是正确的，如果假设 O(1) 乘法，则它是 O(log logn)。

一个简单的方法是：

x_n+1 = x_n²。

取 x₁ = a。

记录日志。

t_n = log x_n

然后
t_n+1 = 2t_n

剩下的就交给你了。

如果考虑两个 k 位数字相乘的复杂性，事情会变得更有趣。

Answer 3

循环迭代次数为Ο(log log n)。循环体本身执行赋值（我们可以将其视为常量）和乘法。迄今为止最著名的乘法算法的步长复杂度为 Ο(n log n×2^{Ο(log* n)})，因此，总而言之，复杂度是喜欢：

Ο(log log n × n log n×2^{Ο(log* n)})

更易读的形式：

Ο(log log n × n log n×2^Ο(log* n)) http://TeXHub.Com/b/TyhcbG9nXGx vZyBuXCxcdGltZXNcLG4gXGxvZyBuXCxcdGltZXNcLDJee08oXGxvZ14qIG4pfSk=

Answer 4

第 i 次迭代 (i=0,1,...) 后，a 的值为 3²ⁱ。将有 O(log log n) 次迭代，假设算术运算的时间复杂度为 O(1)。