如何找到 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("Hello\n");
    else
    {
        f(n - 1);
        f(n - 1);
    }
}
f(N);

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

有人可以解释一下如何找到第一个和第二个算法的复杂度吗？

Answer 1

第一个算法：

如所写，a、b 是 int 而不是 float 毫无意义，我会假设后者。还有 N 而不是 N-1.

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