c-如何找到while循环和递归算法的复杂性

Question

我正试图确定给定算法的复杂性如何随着N.而增长

1.
float epsilon = 0.001;
int a = 0;
int b = N - 1;
while (b - a > epsilon)
{
int m = (int)((b + a) / 2);
if (arr[m] > 0)
b = m;
else
a = m;
}
2.
void f(int n)
{
if (n == 0)
printf("Hellon");
else
{
f(n - 1);
f(n - 1);
}
}
f(N);

对于第一个，我认为它将是o(n(=n，但我不确定。

有人能解释一下如何找到第一个和第二个算法的复杂性吗

Answer 1

第一个算法：

正如所写的，a、b是ints而不是floats是没有意义的，我假设后者。也用N代替N-1。

观察到，在每次迭代中，只要超过epsilon，a和b之间的距离就会减半。因此，迭代次数为ceiling(lg(N/epsilon))，即从N减少到小于epsilon所需的时间。