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

Question

Я новичок в понимании асимптотического анализа 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)   

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

Answer 1

Для первого внутреннего 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).

Answer 2

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

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). Для решения см. .