Когда сумма ряда 1 + 1/2 + 1/3 + 1/4 + ...... + 1 / n = log n, а когда та же сумма равна n, т.е. 1 + 1/2 + 1/3 + 1/4 + ...... + 1 / п = п - PullRequest
Новая
       10

Когда сумма ряда 1 + 1/2 + 1/3 + 1/4 + ...... + 1 / n = log n, а когда та же сумма равна n, т.е. 1 + 1/2 + 1/3 + 1/4 + ...... + 1 / п = п

0 голосов
/ 13 января 2020

Я новичок в понимании асимптотического анализа c, пытаясь найти большое обозначение O, в нескольких задачах оно дается как log n для того же упрощения рядов и n для другой задачи.

Вот вопросы: 

int fun(int n)
{
    int count = 0;
    for (int i= n; i> 0; i/=2)
        for (int j = 0; j < i; j++)
            count ++;
    return count;
} 

T(n)=O(n)

int fun2(int n)
{
    int count = 0;
    for(i = 1; i < n; i++)
        for(j = 1; j <= n; j += i)
            count ++;
    return count;
}

T(n)=O(n log n)

Я действительно запутался. Почему сложности этих, казалось бы, похожих алгоритмов различны?

Ответы [ 2 ]

3 голосов
/ 13 января 2020

Для первого внутреннего l oop работает приблизительно (в точности, если n является степенью 2) 

n + n/2 + n/4 + n/8 + ... + n/2^log2(n)

раз. Это может быть учтено в 

n * (1 + 1/2 + 1/4 + 1/8 + ...  + (1/2)^(log2 n))

2-й фактор называется (частичная сумма) геометрия c ряд , которая сходится , что означает, что, как мы приблизиться к бесконечности, это приблизится к константе. Следовательно, это θ(1); умножив это на n, вы получите θ(n)

Я провел анализ последнего алгоритма всего пару дней go. Число итераций для n в этом алгоритме составляет 

ceil(n) + ceil(n / 2) + ceil(n/3) + ... + ceil(n/n)

Это очень близко к частичной сумме гармоник c серии , умноженной на n: 

n * (1 + 1/2 + 1/3 + 1/4 + ... 1/n)

В отличие от геометрии серии c, серии гармоник c не сходятся, но расходятся по мере добавления новых терминов. Частичные суммы первых n членов могут быть ограничены сверху и снизу ln n + C, следовательно, временная сложность всего алгоритма составляет θ(n log n).

2 голосов
/ 13 января 2020

Серии, сформированные в обоих случаях, отличаются Анализ сложности времени

  1. В этом случае сначала i будет n, а l oop для j будет go до n, затем i будет n/2, а * oop будет go до n/2 и так далее, поэтому сложность времени будет 

     = n + n/2 + n/4 + n/8.......

    Результат этой суммы равен 2n-1 и, следовательно, временная сложность O (n)

  2. В этом случае, когда i равно n, мы будем l oop для j n раз, в следующий раз i будет 2, и мы пропустим одну запись за раз, что означает, что мы повторяем n/2 раз, и так далее. Таким образом, сложность времени будет 

     = n + n/2 + n/3 + n/4........
 = n (1 + 1/2 + 1/3 + 1/4 +....)
 = O(nlogn)

    . Сумма 1 + 1/2 + 1/3 ... равна O (logn). Для решения см. .

...