N-й корень непонимания сложности числа - PullRequest
Новая
       16

N-й корень непонимания сложности числа

0 голосов
/ 02 июня 2018 
#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) сбивает меня с толку.

1 Ответ

0 голосов
/ 02 июня 2018

Внешний цикл выполняет двоичный поиск, который делит диапазон поиска пополам на каждой итерации.Это будет продолжаться до тех пор, пока диапазон поиска не будет уменьшен до 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)).

...