13. Сложность программ с циклами

---

ВПЕРЁД ⇒

Сложность рекурсивных программ

⇐ НАЗАД

Сортировка вставками (insertion sort)

---

Сложность программ с циклами

Невложенный цикл for

for i = 0..n-1
    do_something(i)

Для случая использования невложенных for-циклов количество выполняемых итераций равно $n$. Если сложность вычислений для одной итерации постоянна и равна $k$, то сложность вычислений всего алгоритма равна $k\cdot n$. Таким образом, получаем, что $T(n)=O(n)$, то есть время работы алгоритма линейно зависит от $n$.

Вложенные циклы for

Простой случай вложенных циклов

for i = 0..n-1
    for j = 0..n-1
        do_something(i, j)

В представленном случае каждый из циклов содержит $n$ итераций, тогда всего итераций с вызовом do_something(i, j) в алгоритме будет $n^2$, откуда следует $T(n)=O(n^2)$.

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

for i = 0..n-1
    for j = 0..n-1
        for k = 0..n-1
            do_something(i, j, k) // O(n^3)


for i = 0..n-1
    for j = 0..n-1
        for k = 0..n-1
            for l = 0..n-1
                do_something(i, j, k, l) // O(n^4)

Сложный случай вложенных циклов

Предположим, что имеется следующая ситуация:

for i = 0..n-1
    for j = 0..i
        do_something(i, j)

В данном случае количество итераций вложенного цикла уже зависит от $i$. Как же быть в этом случае? Задача получения оценки сложности алгоритма в этом случае может быть решена несколькими способами.

Грубая оценка временной сложности

Число итераций вложенного цикла for j = 0..i для каждой из итераций внешнего цикла for i = 0..n-1 не превышает $n$. То есть временная сложность работы алгоритма не будет превышать временную сложность ранее рассмотренного алгоритма:

for i = 0..n-1
    for j = 0..n-1
        do_something(i, j)

Из этого следует: $T(n)=O(n^2)$.

Точная оценка временной сложности

Сложность вычислений рассматриваемого алгоритма можно выразить в виде следующей формулы:

$T(n)=\sum _{i=0}^{n-1}{a}_i$, где $a_i$ - временная сложность $i$-й итерации внешнего цикла.

Элементы $a_i$ отображают число итераций внутреннего цикла и изменяются следующим образом:

$a_0=1$, $a_1=2$, …, $a_{n-1}=n$

Из характера изменения элементов $a_i$ видно, что они представляют собой члены арифметической прогрессии, так как каждый последующий элемент отличается от предыдущего на одну и ту же величину: $a_{k+1}=a_k+1$. Тогда $T(n)=\sum _{i=0}^{n-1}{a}_i$ - это сумма членов указанной арифметической прогрессии.

Сумма членов арифметической прогрессии считается по следующей формуле:

$S_n=\sum _{i=0}^{n-1}{a}_i=a_0+a_1+...+a_{n-1}=\frac{a_0+a_{n-1}}{2}\cdot n$

Таким образом, для нашего исследуемого алгоритма получаем:

$T(n)=\sum _{i=0}^{n-1}{a}_i=\frac{a_0+a_{n-1}}{2}\cdot n=\frac{1+n}{2}\cdot n=\frac{n^2}{2}+\frac{n}{2}=O(n^2)$

Графический способ получения оценки сложности вычислений

На рисунке-гистограмме показаны элементы упомянутой арифметической прогрессии, которая отражает процесс изменения количества итераций внутреннего цикла программы с ростом порядкового номера итерации внешнего цикла.

for i = 0..n-1
    for j = 0..i
        do_something(i, j)

Необходимо оценить сумму указанных элементов. Сумма элементов - площадь фигуры, образованной синими столбцами (площадь синего треугольника). Очевидно, что площадь синего треугольника - половина площади красного квадрата (в котором расположен треугольник). Площадь красного квадрата равна $O(N^2)$, тогда площадь синего треугольника равна $O(N^2/2)$ . Таким образом, получаем:

$T(n)=O(n^2/2)=O(n^2)$.

Цикл while, вложенный в цикл for

for i = 0..n-1
    j = 0
    while j*j <= i // граница i будет достигнута при j равном
                   // квадратному корню из i
        do_something(i, j)
        j = j + 1

Упрощаем процесс анализа путём замены условия в цикле while:

for i = 0..n-1
    j = 0
    while j*j <= n // граница n будет достигнута при j равном
                   // квадратному корню из n
        do_something(i, j)
        j = j + 1

$T(n)=O(n\sqrt[2]{n})$

---

ВПЕРЁД ⇒

Сложность рекурсивных программ

⇐ НАЗАД

Сортировка вставками (insertion sort)

---

Источники

• Павел Маврин “АиСД, Семестр 1, Лекция 1. Оценка времени. Сортировка слиянием”
• Арифметическая прогрессия (Wiki)

Категория

Алгоритмы-и-структуры-данных Алгоритмы-и-структуры-данных

Теги

• Алгоритм Алгоритм
• Цикл Цикл
• Время-работы Время-работы
• Сложность-по-времени Сложность-по-времени
• Временная-сложность Временная-сложность
• Time-complexity Time-complexity
• Сложность-вычислений Сложность-вычислений
• Big-O Big-O
• Арифметическая-прогрессия Арифметическая-прогрессия