Введение в анализ сложности алгоритмов (часть 2)

От переводчика: данный текст даётся с незначительными сокращениями по причине местами излишней «разжёванности» материала. Автор абсолютно справедливо предупреждает, что отдельные темы могут показаться читателю чересчур простыми или общеизвестными. Тем не менее, лично мне этот текст помог упорядочить имеющиеся знания по анализу сложности алгоритмов. Надеюсь, что он окажется полезен и кому-то ещё.
Из-за большого объёма оригинальной статьи я разбила её на части, которых в общей сложности будет четыре.
Я по прежнему буду крайне признательна за любые замечания в личку по улучшению качества перевода.

Опубликовано ранее:
Часть 1

Сложность

Из предыдущей части можно сделать вывод, что если мы сможем отбросить все эти декоративные константы, то говорить об асимптотике функции подсчёта инструкций программы будет очень просто. Фактически, любая программа, не содержащая циклы, имеет f( n ) = 1, потому что в этом случае требуется константное число инструкций (конечно, при отсутствии рекурсии — см. далее). Одиночный цикл от 1 до n, даёт асимптотику f( n ) = n, поскольку до и после цикла выполняет неизменное число команд, а постоянное же количество инструкций внутри цикла выполняется n раз.

Руководствоваться подобными соображениями менее утомительно, чем каждый раз считать инструкции, так что давайте рассмотрим несколько примеров на закрепление этого материала. Следующая PHP-программа проверяет, содержится ли в массиве A размера n заданное значение:

<?php
    $exists = false;
    for ( $i = 0; $i < n; ++$i ) {
        if ( $A[ $i ] == $value ) {
            $exists = true;
            break;
        }
    }
?>

Такой метод поиска значения внутри массива называется линейным поиском. Это обоснованное название, поскольку программа имеет f( n ) = n (что означает «линейный» более точно, мы рассмотрим в следующем разделе). Инструкция break позволяет программе завершиться раньше, даже после единственной итерации. Однако, напоминаю, что нас интересует самый неблагоприятный сценарий, при котором массив A вообще не содержит заданное значение. Поэтому f( n ) = n по-прежнему.

Давайте рассмотрим программу на Python, которая складывает два значения из массива и записывает результат в новую переменную:

v = a[ 0 ] + a[ 1 ] 

Здесь у нас постоянное количество инструкций, следовательно, f( n ) = 1.

Следующая программа на C++ проверяет, содержит ли вектор (своеобразный массив) A размера n два одинаковых значения:

bool duplicate = false;
for ( int i = 0; i < n; ++i ) {
    for ( int j = 0; j < n; ++j ) {
        if ( i != j && A[ i ] == A[ j ] ) {
            duplicate = true;
            break;
        }
    }
    if ( duplicate ) {
        break;
    }
}

Два вложенных цикла дадут нам асимптотику вида f( n ) = n².

---

Практическая рекомендация: простые программы можно анализировать с помощью подсчёта в них количества вложенных циклов. Одиночный цикл в n итераций даёт f( n ) = n. Цикл внутри цикла — f( n ) = n². Цикл внутри цикла внутри цикла — f( n ) = n³. И так далее.

---

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

int i;
for ( i = 0; i < n; ++i ) {
    f( n );
}

Если нам известно, что f( n ) выполняет ровно n команд, то мы можем сказать, что количество инструкций во всей программе асимптотически приближается к n², поскольку f( n ) вызывается n раз.

---

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

---

А сейчас давайте переключимся на интересную систему обозначений, используемую теоретиками. Когда мы выясняем точную асимптотику f, мы говорим, что наша программа — Θ( f( n ) ). Например, в примерах выше программы Θ( 1 ), Θ( n² ) и Θ( n² ), соответственно. Θ( n ) произносится как «тета от n». Иногда мы говорим, что f( n ) (оригинальная функция подсчёта инструкций, включая константы) есть Θ( что-то ). Например, можно сказать, что f( n ) = 2n — это функция, являющаяся Θ( n ). В общем, ничего нового. Можно так же написать, что 2n ∈ Θ( n ), что произносится: «два n принадлежит тета от n». Пусть вас не смущает такая нотация: она просто говорит о том, что если мы посчитаем количество необходимых программе команд, и оно будет равно 2n, то асимптотика этого алгоритма описывается как n (что мы находим, отбрасывая константу). Имея данную систему обозначений, приведём несколько истинных математических утверждений:

1. n⁶ + 3n ∈ Θ( n⁶)
2. 2ⁿ + 12 ∈ Θ( 2ⁿ )
3. 3ⁿ + 2ⁿ ∈ Θ( 3ⁿ )
4. nⁿ + n ∈ Θ( nⁿ )

Кстати, если вы решили упражнение 1 из первой части, то это его правильный ответ.

Мы называем эту функцию (т.е. то, что пишем Θ( здесь )) временной сложностью, или просто сложностью нашего алгоритма. Таким образом, алгоритм с Θ( n ) имеет сложность n. Также существуют специальные названия для Θ( 1 ), Θ( n ), Θ( n² ) и Θ( log( n ) ), потому что они встречаются очень часто. Говорят, что Θ( 1 ) — алгоритм с константным временем, Θ( n ) — линейный, Θ( n² ) — квадратичный, а Θ( log( n ) ) — логарифмический (не беспокойтесь, если вы ещё не знаете, что такое логарифм — скоро мы об этом поговорим).

---

Практическая рекомендация: программы с большим Θ выполняются медленнее, чем с маленьким.

---

Нотация «большое О»

В реальной жизни иногда проблематично выяснить точно поведение алгоритма тем способом, который мы рассматривали выше. Особенно для более сложных примеров. Однако, мы можем сказать, что поведение нашего алгоритма никогда не пересечёт некой границы. Это делает жизнь проще, так как чёткого указания на то, насколько быстр наш алгоритм, у нас может и не появиться, даже при условии игнорирования констант (как раньше). Всё, что нам нужно — найти эту границу, а как это сделать — проще объяснить на примере.

Наиболее известной задачей, которую используют при обучении алгоритмам, является сортировка. Даётся массив A размера n (звучит знакомо, не так ли?), и нас просят написать программу, его сортирующую. Интерес тут в том что, такая необходимость часто возникает в реальных системах. Например, обозревателю файлов нужно отсортировать файлы по имени, чтобы облегчить пользователю навигацию по ним. Или другой пример: в видео игре может возникнуть проблема сортировки 3D объектов, демонстрируемых на экране, по их расстоянию от точки зрения игрока в виртуальном мире, чтобы определить, какие из них будут для него видимы, а какие — нет (это называется Visibility Problem). Сортировка также интересна тем, что для неё существует множество алгоритмов, одни из которых хуже, чем другие. Так же эта задача проста для определения и объяснения. Поэтому давайте напишем кусок кода, который будет сортировать массив.

b = []
n.times do
    m = a[ 0 ]
    mi = 0
    a.each_with_index do |element, i|
        if element < m
            m = element
            mi = i
        end
     end
     a.delete_at( mi )
     b << m
end

Перед вами совершенно неэффективный способ реализации сортировки массива на Ruby. (Конечно, Ruby поддерживает сортировку массивов с использованием встроенных функций, которые и следует использовать. Они несомненно быстрее, чем код выше, представленный исключительно для иллюстрации.)

Этот метод называется сортировкой выбором. Сначала находится минимальный элемент массива (a в коде выше. Минимум обозначен как m, а его индекс — как mi), который помещается в конец нового массива (b в нашем случае) и удаляется из оригинального. Затем среди оставшихся значений снова находится минимум, добавляется в новый массив (который теперь содержит два значения) и удаляется из старого. Процесс повторяется, пока все элементы не будут перенесены из первоначального в новый массив, что будет означать конец сортировки. В нашем примере мы имеем два вложенных цикла. Внешний цикл «пробегает» n раз, а внутренний — по разу для каждого элемента массива a. Поскольку изначально a имеет n элементов и на каждой итерации мы удаляем один из них, то сначала внутренний цикл «прокручивается» n раз, потом n - 1, n - 2 и так далее, пока на последней итерации внутренний цикл не пройдёт всего один раз.

Если рассматривать сумму 1 + 2 + ... + (n - 1) + n, то найти сложность этого кода будет несколько проблематично. Но мы можем найти для неё «верхний предел». Для этого мы изменим программу (можно мысленно, не трогая код), чтобы сделать её хуже, чем она есть, а затем выведем сложность для того, что получилось. Тогда можно будет уверенно сказать, что оригинальная программа работает или также плохо, или (скорее всего) лучше.

Давайте теперь подумаем над тем, как нам изменить программу, чтобы упростить для неё вывод сложности. Не забывайте: мы можем только ухудшать её (например, добавляя в код новые инструкции), чтобы наша оценка имела смысл для оригинальной программы. Очевидно, что мы можем изменить внутренний цикл программы, заставив его вычисляться n раз на каждой итерации. Некоторые из этих повторений буду бесполезны, но зато это поможет нам проанализировать сложность результирующего алгоритма. Если мы внесём это небольшое изменение, то наш новый алгоритм будет иметь Θ( n²), поскольку получим два вложенных цикла, каждый из которых выполняется ровно n раз. А если это так, то оригинальный алгоритм имеет O( n² ). O( n² ) произносится как «большое О от n в квадрате». Это говорит о том, что наша программа асимптотически не хуже, чем n². Она будет работать или лучше, или также. Кстати, если код действительно имеет Θ( n²), то мы всё ещё говорим, что он O( n² ). Чтобы лучше понять это, представьте, что изменение оригинальной программы меняет её не сильно, делая лишь чуть-чуть хуже. Примерно как от добавления бесполезных инструкций в начало программы. Это изменит только константу в функции подсчёта инструкций, которую мы проигнорируем в асимптотике. Таким образом, Θ( n²) для программы — это и O( n² ) тоже.

А вот обратное верно не всегда. Например, любой код с Θ( n ) также и O( n² ) в дополнение к O( n ). Если мы представим, что Θ( n ) программа — это просто цикл for, который выполняется n раз, мы можем сделать его хуже, добавив внутрь ещё один for, тоже повторяющийся n раз. Это даст программу с f( n ) = n². Обобщая: любая программа с Θ( a ) является O( b ) при b худшем, чем a. Заметьте также, что изменение не обязательно должно иметь смысл или создавать код, аналогичный исходному. Всё, что от него требуется — увеличить количество инструкций по отношению к заданному n. Мы используем результат для подсчёта инструкций, а не для решения проблемы.

Итак, говоря, что программа имеет O( n² ), мы находимся в безопасности: анализ алгоритма показал, что он никогда не будет работать хуже, чем n². Это даёт нам хорошую оценку того, насколько быстра наша программа. Давайте прорешаем несколько примеров, чтобы вы получше освоились с новой нотацией.

Поскольку О-сложность алгоритма представляет собой верхний предел его настоящей сложности, которую, в свою очередь, отображает Θ, то иногда мы говорим, что Θ даёт нам точную оценку. Если мы знаем, что найденная нами граница не точна, то можем использовать строчное о, чтобы её обозначить. Например, если алгоритм является Θ( n ), то его точная сложность — n. Следовательно, этот алгоритм O( n ) и O( n² ) одновременно. Поскольку алгоритм Θ( n ), то O( n ) определяет границу более точно. А O( n² ) мы можем записать как о( n² ) (произносится: «маленькое o от n в квадрате»), чтобы показать, что мы знаем о нестрогости границы. Конечно, лучше, когда мы можем найти точные границы для нашего алгоритма, чтобы иметь больше информации о его поведении, но, к сожалению, это не всегда легко сделать.

---

Практическая рекомендация: выяснить O-сложность алгоритма проще, чем его Θ-сложность.

---

К настоящему моменты вы могли уже порядком запутаться во всех этих новых обозначениях, но давайте познакомимся с ещё двумя символами перед тем, как перейти к дальнейшим примерам. Выше мы меняли нашу программу, чтобы сделать её хуже (увеличили количество инструкций и, таким образом, время выполнения), чем создали O-нотацию. О говорит нам о том, что наш код никогда не будет работать медленнее определённого предела. Из этого мы получаем основания для оценки: достаточно ли хороша наша программа? Если же мы поступим противоположным образом, сделав имеющийся код лучше, и найдём сложность того, что получится, то мы задействуем Ω-нотацию. Таким образом, Ω даёт нам сложность, лучше которой наша программа быть не может. Она полезна, если мы хотим доказать, что программа работает медленно или алгоритм является плохим. Так же её можно применить, когда мы утверждаем, что алгоритм слишком медленный для использования в данном конкретном случае. Например, высказывание, что алгоритм является Ω( n³ ), означает, что алгоритм не лучше, чем n³. Он может быть Θ( n³ ), или Θ( n⁴ ), или ещё хуже, но мы будем знать предел его «хорошести». Таким образом, Ω даёт нам нижнюю границу сложности нашего алгоритма. Аналогично ο, мы можем писать ω, если знаем, что этот предел нестрогий. Например, Θ( n³ ) алгоритм является ο( n⁴ ) и ω( n² ). Ω( n ) произносится как «большое омега от n», в то время как ω( n ) произносится «маленькое омега от n».

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

Если вы не до конца запомнили всё это многообразие обозначений, не стоит переживать. Вы всегда можете вернуться и освежить в памяти информацию по ним. Наиболее важные символы — это O и Θ.

Заметьте также, что хотя Ω и даёт нам нижний предел поведения нашей функции (т.е. мы улучшаем программу, чтобы она вычисляла меньшее количество инструкций), мы всё ещё ссылаемся на анализ наихудшего случая. Это происходит потому, что мы подаём на вход программы наихудший набор данных и анализируем её поведение.

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

Оператор сравнения асимптотических оценок	Оператор сравнения чисел
Алгоритм является o( что-то )	Число < чего-то
Алгоритм является O( что-то )	Число ≤ чего-то
Алгоритм является Θ( что-то )	Число = чему-то
Алгоритм является Ω( что-то )	Число ≥ чего-то
Алгоритм является ω( что-то )	Число > чего-то

---

Практическая рекомендация: несмотря на то, что все символы O, o, Ω, ω и Θ необходимы время от времени, O используется чаще всего, поскольку его проще найти, чем Θ, и оно более полезно на практике, чем Ω.

---

Автор: AveNat

Источник