algorithm - 如何找到这个功能的复杂性？

Question

我得到了 log n 但它不是 log n 它是 log(log n)
但为什么？

int function(int n){
  return aux(n , 2)
}

int aux(int n, int x){
  while (n<x) {
    x *= x;
  }
  return x;  
}

函数的复杂度是多少？

Answer 1

很确定循环条件应该是 n > x 所以我会在这个答案中假设它。

首先，观察x的值:

x1 = x0 * x0
   = 2 * 2
   = 2^2
x2 = x1 * x1 
   = x0 * x0 * x0 * x0
   = 2 * 2 * 2 * 2
   = 2^4
x3 = x2 * x2
   = x1 * x1 * x1 * x1 
   = x0 * x0 * x0 * x0 * x0 * x0 * x0 * x0
   = 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2
   = 2^8

我们看到指数增长为 2^t，其中 t 是循环中的迭代次数，因此我们可以获得 的封闭形式方程x:

x = 2^(2^t)

然后我们可以求解迭代次数t:

n > x
=> n > 2^(2^t)
=> log(n) > 2^t
=> log(log(n)) > t

根据需要。