Где это работает

Большинство современных вычислительных устройств имеют RAM-модель оперативной памяти.

RAM – Random Access Memory – произвольный доступ к памяти.

RAM модель оперативной памяти представлена массивом, состоящем из ячеек, каждая из которых имеет уникальный индекс (адрес). Каждая ячейка может хранить некоторое количество данных, обычно представленных в виде битов или байтов.

Т.к. RAM модель представлена массивом, то доступ к данным (чтение или запись) в ячейке с любым адресом происходит за постоянное время.

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

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

Что такое сложность алгоритма?

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

Сложность алгоритма описывает, как время работы и/или использование памяти алгоритма увеличивается в зависимости от размера входных данных.

Сложность алгоритма используется для описания поведения алгоритма по мере приближения размера его входных данных к бесконечности.

Т.е. сложность алгоритма – это функция $f(n)$, где $n$ – количество входных данных, описывающая его производительность.

---

Зачем нужно оценивать сложность алгоритма?

1. Предсказание производительности алгоритма
   • Зная сложность алгоритма, можно оценить вычислительные затраты (потенциально время) для выполнения при заданном размере входных данных
2. Сравнение алгоритмов
   • Зная сложности двух алгоритмов, можно сравнить их и выбрать оптимальный для решаемой задачи
3. Оптимизация алгоритмов
   • Большинство алгоритмов состоят из других алгоритмов, поэтому, зная сложность составляющих частей, можно найти более производительное решение и оптимизировать весь алгоритм

---

Почему нельзя оценить производительность алгоритма опытным путём

Можно, но:

• Нужно потратить время на изучение, реализацию и отладку алгоритма
• Результаты могут отличаться друг от друга в зависимости от условий:
  • Запуск на различных устройствах и/или операционных системах
  • Запуск при различной нагрузке на устройство
  • Различное время простоя процессора
  • и многие другие
• На выполнение алгоритма может не хватить ресурсов

Соответственно, теоретическая оценка сложности алгоритма позволит быстро понять, подходит ли алгоритм для решения задачи или нет.

---

Виды сложности

По ресурсам:

• Временная – зависимость количества операций, совершённых алгоритмом, от размера входных данных
• Пространственная – зависимость использованной оперативной памяти от размера входных данных

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

Существуют 3 случая:

• Худший случай – оценка сложности алгоритма для входных данных, требующих максимальные временные и/или пространственные затраты для решения задачи
• Средний случай – оценка сложности алгоритма для случайных входных данных, т.е. это математическое ожидание сложности работы алгоритма при случайных входных данных
• Лучший случай – оценка сложности алгоритма для входных данных, требующих минимальные временные и/или пространственные затраты для решения задачи, т.е. созданы идеальные условия для работы алгоритма

---

Функции, использующиеся для оценки сложности алгоритма

* Функции ниже записаны от наиболее производительной до наименее производительной.

1. $1$ – постоянная сложность алгоритма, не зависит от размера входных данных
2. $\log_b (n)$ – логарифмическая сложность алгоритма
   • Под функцией $\log(n)$ обычно подразумевается $\log_2(n)$
3. $n^p$ – степенная сложность алгоритма
   • Примеры: $\sqrt{n}$, $n$, $n^2$, $n^3$ и т.д.
4. $x^n$ – показательная сложность алгоритма
   • Примеры: $2^n$, $4^n$
5. $n!$ – факториальная сложность алгоритма

---

O-большое (O)

Эта математическая нотация (функция) показывает верхнюю границу сложности алгоритма и даёт оценку сложности алгоритма в худшем случае.

Пусть функция $f(n)$, где $n$ – количество входных данных, представляет действительную сложность алгоритма. Тогда сложность этого алгоритма в O-нотации определяется как $O(g(n))$, если существуют $C$ и $n_0$ такие, что для $n \ge n_0$ и $C \gt 0$ функция $f(n)$ ограничена сверху функцией $C \bullet g(n)$, а $g(n)$ – известная функция. $f(n) \le C \bullet O(g(n))$ То есть, если алгоритм имеет временную сложность в O-нотации $O(g(n))$, то время, необходимое для его выполнения, растёт не быстрее, чем $C \bullet g(n)$.

---

Омега-большое (Ω)

Эта математическая нотация демонстрирует нижнюю границу сложности алгоритма и даёт оценку сложности алгоритма в лучшем случае.

Пусть функция $f(n)$, где $n$ – количество входных данных, представляет действительную сложность алгоритма. Тогда сложность этого алгоритма в Ω-нотации определяется как $\Omega(g(n))$, если существуют $C$ и $n_0$ такие, что для $n \ge n_0$ и $C \gt 0$ функция $f(n)$ ограничена снизу функцией $C \bullet g(n)$, а $g(n)$ – известная функция. $f(n) \ge C \bullet \Omega(g(n))$ То есть, если алгоритм имеет временную сложность в Ω-нотации $\Omega(g(n))$, то время, необходимое для его выполнения, растёт не медленее, чем $C \bullet g(n)$.

---

Тета-большое (Θ)

Эта математическая нотация даёт оценку сложности алгоритма в среднем случае.

Если сложность алгоритма в O-нотации равна $O(g(n))$ и в Ω-нотации равна $\Omega(g(n))$, то в Θ-нотации сложность алгоритма также равна $\Theta(g(n))$.

Пусть функция $f(n)$, где $n$ – количество входных данных, представляет действительную сложность алгоритма. Тогда сложность этого алгоритма в Θ-нотации определяется как $\Theta(g(n))$, если существуют $C_1$, $C_2$ и $n_0$ такие, что для $n \gt n_0$ и $C_2 \ge C_1 \gt 0$ функция $f(n)$ ограничена снизу функцией $C_1 \bullet \Theta(g(n))$ и ограничена сверху функцией $C_2 \bullet \Theta(g(n))$, а $g(n)$ – известная функция. $C_1 \bullet \Theta(g(n)) \le f(n) \le C_2 \bullet \Theta(g(n))$ То есть если алгоритм имеет временную сложность в Θ-нотации $\Theta(g(n))$, то время, необходимое для его выполнения, растёт не медленнее, чем $C_1 \bullet g(n)$, и не быстрее, чем $C_2 \bullet g(n)$.

---

O-малое (o)

Эта математическая нотация также используется для анализа сложности алгоритма в худшем случае и демонстрирует верхнюю границу сложности алгоритма, которую невозможно достичь.

Она используется, когда необходимо показать, что производительность одного алгоритма строго лучше производительности другого.

Пусть функция $f(n)$, где $n$ – количество входных данных представляет действительную сложность алгоритма. Тогда сложность этого алгоритма в o-нотации определяется как $o(g(n))$, если для всех $n \ge n_0$ выполняется: $\lim_{n \to \infty} \frac{f(n)}{g(n)} = 0$ $g(n)$ – известная функция.

---

Омега-малое (ω)

Эта математическая нотация используется для анализа сложности алгоритма в лучшем случае и демонстрирует нижнюю границу сложности алгоритма, которую невозможно достичь.

Аналогично o-нотации, она используется, когда необходимо сравнить алгоритмы, но в их лучшем случае.

Пусть функция $f(n)$, где $n$ – количество входных данных представляет действительную сложность алгоритма. Тогда сложность этого алгоритма вω -нотации определяется как $o(g(n))$, если для всех $n \ge n_0$ выполняется: $\underset{n \to \infty}{\lim} \frac{f(n)}{g(n)} = \infty$ $g(n)$ – известная функция.

---

Как рассчитать сложность алгоритма

Замечания

1. Обычно для алгоритма рассчитываются:
   1. Временная сложность в худшем и среднем случаях
   2. Пространственная сложность в худшем случае
2. Часто константы не имеют значения, поэтому они отбрасываются
3. Младшие члены в многочлене также не учитываются: $3n^2 + 10n + 5$ преобразуется в $n^2$
4. Временная сложность алгоритма рассчитывается в количестве совершаемых элементарных операций

---

Определения

Элементарная операция – операция, сложность которой принимается за $1$. Соответственно, операции аналогичные данной и более производительные имеют такую же сложность.

Рассчёт сложности алгоритма

Сложность алгоритма рассчитывается как сумма элементарных операций, совершённых в течение работы алгоритма.

---

Сложность последовательных операций

Общая сложность последовательных операций равна сумме сложностей каждой операции.

функция f():
    операция1;
    операция2;
    ...
    операцияM;

\begin{gather} O(f) = O(f_{op_1}) + O(f_{op_2}) + \ldots + O(f_{op_m}) = \\ = O(f_{op_1} + f_{op_2} + \ldots + f_{op_m}) = O(1) \end{gather} Если не совершается операций над входными данными, то сложность данной функции равняется $O(1)$.

функция f(array длины N):
    операция1;
    nlogn_sort(array); // сложность nlogn
    операция2;

Сложность данной функции f также рассчитывается, как сумма сложностей каждой операции. Т.к. одна из операций имеет сложность $O(n \log_2n)$, то сложность всей функции становится $O(n log_2n)$.

---

Сложность условий

если условие1:
    блок_условий1
    ...
иначе если условие2:
    блок_условий2
    ...
иначе если ...
    ...
иначе если условиеM:
    блок_условийM
    ...
иначе:
    блок_условийM+1
    ...

Сложность условий рассчитывается исходя из наиболее сложного блока: $O(f_{condition}) = max(O(f_{блок_1}), O(f_{блок_2}), O(f_{...}), O(f_{блок_m}), O(f_{блок_{m + 1}}))$

---

Сложность цикла

цикл для i от 1 до N:
    блок_операций

Цикл можно представить как повторение одного и того же блока операций N раз, следовательно сложность цикла можно представить как: $O(f_{cycle}) = O(f_{блок} + ... f_{блок}) = O(N \bullet f_{блок})$

Следовательно, сложность цикла выражается произведением сложности операций внутри цикла и количества повторений цикла.

Если количество повторений цикла не зависит от входных данных, то количество повторений считается константным. Следовательно: $O(f_{cycle}) = O(f_{блок})$

цикл для i от 1 до 10:
    блок_операций

Также циклы могут иметь нелинейную сложность. Например, бинарный поиск выполняется со сложностью $O(\log_2 n)$, а генерация перестановок за $O(n!)$.

---

Сложность вложенных циклов

цикл для i от 1 до k:
    цикл для j от 1 до m: // цикл для j = блок_i
        блок_j;

Т.к. цикл для j – это блок операций цикла для i, то получим: $O(f_{cycle_i}) = O(k \bullet f_{блок_i})$ Т.к. $блок_i$ – цикл j, то получим: $O(f_{cycle_j}) = O(f_{блок_i}) = O(m \bullet f_{блок_j})$ Следовательно: $O(f_{cycle_i}) = O(k \bullet m \bullet f_{блок_j})$ Сложность вложенных циклов равна произведению сложностей каждого цикла.

---

Сложность рекурсии

Общий подход к подсчёту сложности рекурсивного алгоритма – определение функции роста дерева рекурсивных вызовов.

То есть необходимо понять, сколько рекурсивных вызовов совершает функция на каждом шаге и до какой глубины это будет происходить (когда вызовы остановятся).

Объяснение на рекурсивном алгоритме поиска n-го члена последовательности Фиббоначчи

Алгоритм:

функция fib(n):
    # 0 1 1 2 3 5 8 13 ...
    если n < 2:
        вернуть n
    вернуть fib(n - 1) + fib(n - 2)    

Если вызвать функцию fib(5), то получится данное дерево рекурсивных вызовов

fib(5)
    - fib(4)
        - fib(3)
            - fib(2)
                - fib(1)
                - fib(0)
            - fib(1)
        - fib(2)
            - fib(1)
            - fib(0)
    - fib(3)
        - fib(2)
            - fib(1)
            - fib(0)
        - fib(1)

На каждом вызове функции fib происходит 2 рекурсивных вызова, эти вызовы будут происходит, пока значение n не станет равным 0 или 1. Т.к. каждый раз передаваемое в функцию значение уменьшается на 1 или на 2, то потребуется n таких вызовов.

Соответственно, если на каждом вызове функции происходит 2 рекурсивных вызова и таких вызовов n, то сложность данного алгоритма равна: $2 \bullet 2 \bullet 2 \bullet \dots \bullet 2$ – n раз, т.е. $2^n$.

Геометрический подход

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

Суть данного вида алгоритмов заключается в использовании стратегии "Разделяй и властвуй". Это значит, что на каждом рекурсивном вызове функции количество обрабатываемых данных уменьшается в 2 раза.

Например, для массива чисел от 1 до 8 разделение будет выглядеть так:

Получился прямоугольник, длина которого равна $n$, а высота $\log_2(n)$, т.к. с каждым вызовом функции, количество обрабатываемых данных в ней уменьшается в 2 раза.

Тогда сложность этого алгоритма можно рассчитать как площадь данной фигуры: $n \bullet \log_2(n)$.

Сложность структур данных и амортизационный анализ

Амортизационный анализ — это метод анализа вычислительной сложности алгоритма, когда время исполнения одного шага алгоритма, умноженное на число шагов, даёт бОльшую оценку на время его исполнения по сравнению с реальной.

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

Рассмотрим последовательность операций $op_1, op_2, \dots, op_n$. Пусть каждая операция $op_i$ выполняется за фактическое время $t_i$. Для каждой операции нужно посчитать амортизационное время $a_i$, такое что: $\forall j: \sum_{i=1}^j a_i \ge \sum_{i=1}^j t_i$

Рассмотрим структуру данных, содержащую стек, которая поддерживает операцию popMpushX:

function popMpushX(stack, m, x):
    for i in [0, m):
        stack.pop()
    stack.push(x)

Предполагается, что размер хранимого в структуре данных стека больше m. Также предполагается, что данная операция выполняется за $m + 1$ операций.

Можно заметить, что если совершить $n$ таких операций, удаляющих все элементы из стека размера $n$ на каждом шаге ($m = n$), то сложность всех операций в сумме будет равняться $n \bullet (n + 1) = O(n^2)$.

Амортизационный анализ позволит оценить действительную сложность таких операций.

Метод банкира (бухгалтерский метод)

Суть метода заключается в том, что каждой операции выдаётся $d_i$ монет и разрешается тратить $c_i$ монет. При этом все доступные монеты операция может разложить по структуре данных. Тогда амортизационная стоимость одной операции составит $a_i = t_i + d_i - c_i$.

Чтобы выполнялось условие $\forall j: \sum\limits_{i=1}^j a_i \ge \sum\limits_{i=1}^j t_i$ необходимо ввести ограничение: невозможно потратить больше монет, чем их существует, т.е. – $\sum\limits_{i=1}^j d_i - \sum\limits_{i = 1}^j c_i \ge 0$.

Так как $\sum\limits_{i=1}^j a_i = \sum\limits_{i=1}^j t_i + \sum\limits_{i=1}^j d_i - \sum\limits_{i=1}^j c_i$, то $\sum\limits_{i=1}^j a_i \ge \sum\limits_{i=1}^j t_i$.

Для совершения операции popMpushX выдадим 1 монету ($d_i = 1$) и определим её на элемент X, который был добавлен в стек. Таким образом будет "оплачена" операция удаления этого элемента X в будущем.

Чтобы удалить $m_i$ элементов из стека, необходимо потратить монеты, лежащие на последних $m_i$ элементах, соответственно $c_i = m_i$.

Тогда амортизационная стоимость каждой операции будет равна $a_i = t_i + d_i - c_i = (m_i + 1) + 1 - m_i = 2$.

Тогда сложность выполнения $n$ таких операция будет равна $\sum\limits_{i=1}^n a_i = 2 \bullet n = O(n)$.

Получается, что амортизационная сложность выполнения $n$ таких операций в худшем случае – $O(n)$, меньше сложности, вычисленной стандартным подходом – $O(n^2)$.

Метод потенциалов

Суть метода заключается в том, что структура данных может принимать несколько состояний. $S_0$ – начальное состояние структуры, $S_i$ – состояние структуры после выполнения $i$-ой операции.

Введём функцию $\phi(s)$, которая будет принимать текущее состояние структуры данных и возвращать неотрицательное число – потенциал структуры на состоянии $s$. При этом $\phi(S_0) = 0$.

Тогда потенциал структуры данных на состоянии $S_i$ – $\phi_i$. А разность потенциалов для перехода из состояния $S_{i-1}$ к $S_i$ как $\Delta \phi_i = \phi_i - \phi_{i-1}$.

Т.к. при переходе из состояния $S_{i-1}$ в состояние $S_i$ нужно совершить 1 операцию push и $m_i$ операций pop, то $\Delta \phi_i = 1 - m_i$.

Тогда амортизационная стоимость операции равна $a_i = t_i + \Delta \phi_i = (m + 1) + (1 - m) = 2$.

Следовательно, амортизационная сложность $n$ таких операций равна $\sum\limits_{i=1}^n a_i = 2 \bullet n = O(n)$.

Агрегационный метод

Суть данного метода заключается в том, что необходимо найти $\sum\limits_{i=1}^n t_i$ и поделить это значение на количество совершённых операций.

Если предположить, что каждая операция удаляет все элементы из стека и добавляет 1, то на выполнение первой операции потребуется 1 действие; на выполнение следующих: $1 + 1$ действий (1 на push, 1 на удаление всех элементов, т.к. в стеке всегда будет 1 элемент).

Соответственно, первая операция будет происходить за 1 действие, другие $n - 1$ операций за 2 действия.

$a_i = \frac{1}{n} \bullet \sum\limits_{i=1}^n t_i = \frac{1 + (n - 1) \bullet 2}{n} = \frac{1}{n} + \frac{2 \bullet n - 2}{n} = 2$

Следовательно, амортизированная сложность $n$ таких операция равна $\sum\limits_{i=1}^n a_i = 2 \bullet n = O(n)$.

---