230问答网 > 分析下列算法的时间复杂度 void f(int n) { int i=1; while (i<=n) i=2*i; }

分析下列算法的时间复杂度 void f(int n) { int i=1; while (i<=n) i=2*i; }

2024-12-24 18:24:49

推荐回答（3个）

回答1：

时间复杂度，就是执行次数最多的那个语句次数。
这段程序中，执行次数最多的就是 i=2*i;
其执行的次数为：

2*2*2*2*...........*2<=n
假设为x次，
则 2^x <=n
2^x =n 可以推出 x = log2n
所以，时间复杂度为 O(log2n)

这里的2是log的下标。

回答2：

设复杂度T(n)
那么T(n) = 1 + T(n/2)
所以T(n) = log2(n)

回答3：

O(n)