数字复杂度误解的 N 次方根

Question

#include <stdio.h>

int main()
{
    double d;
    int n, i;
    double lower=0, upper=1, middle, product;
    scanf("%lf %d", &d, &n);
    if (d>upper) upper=d;
    while (upper-lower>0.000005)
    {
        middle=(upper+lower)/2;
        product=1;
        for (i=0; i<n; i++)
            product*=middle;
        if (product>d) upper=middle;
        else lower=middle;
    }
    printf ("%.5f\n",(lower+upper)/2);
    return 0;
}

为什么这个算法有O(n*log(d/0.000005))复杂度？ (d/0.000005) 部分让我感到困惑。

Answer 1

外层循环是运行二分搜索，每次迭代都会将搜索范围一分为二。它会一直持续到搜索范围缩小到 0.000005。所以问题是，“你需要除以 2 多少次才能将搜索范围从 d（这是起始范围）缩小到 0.000005？答案是 log_2(d/0.000005)。

内部循环运行 n 次。所以总的运行时间正比于

n * log_2(d/0.000005)

但这不是复杂性，因为 big-O 忽略常量。所以 log 的基数被忽略了。并且除法被忽略因为

n * log(d/0.000005) = n * (log(d) - log(0.000005))

所以算法的复杂度是O(n log(d))。

数字复杂度误解的 N 次方根

N-th rooth of the number complexity misunderstanding

algorithm

complexity-theory

big-o