我得到了 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;
}
函数的复杂度是多少?
最佳答案
很确定循环条件应该是 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
根据需要。
关于algorithm - 如何找到这个功能的复杂性?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/37489252/