Анализ алгоритмов: теория

Классификации порядков роста настолько важны, что привели к большому количеству исследований в последние годы. Поговорим об этом коротко.

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

Во многих ситуациях входные данные случайные, и нужно смоделировать их случайность, если сделать это, то появляется способ предсказать быстродействие при широком изменении входных данных. Быстродействие алгоритма 3-SUM почти не меняется. Единственное, что меняется в этом алгоритме, это количество обновления счетчика. Но это не влияет на наш анализ. Для двоичного поиска: искомое может найтись сразу, то есть время постоянное. Можно показать, что в среднем и худшем варианте время равно log2(N). Есть и другие примеры с большей вариативностью, то есть анализ подстраивается под входные данные.

Но что насчет той задачи, которую пытается решить клиент? Придется разобраться и в ней, чтобы понимать быстродействие алгоритма. Есть два надежных подхода. Один в том, чтобы писать алгоритм под худший сценарий. Тогда он всегда будет работать быстро. Если это не удается, то ориентироваться на случайность данных, полагаясь на вероятностную гарантию. Мы увидим примеры обоих подходов.

Рассуждения подобного толка приводят к обсуждению того, что я называю теорией алгоритмов. Наша цель: есть задача, например, 3-SUM, и мы хотим понять, насколько она сложная. Хотим найти лучший алгоритм для её решения. Программисты используют следующий подход: они стремятся исключить из анализа как можно больше факторов, свести анализ времени к одной постоянной величине. Применяется порядок роста. Нас не заботит входная модель. Сосредотачиваемся на разборе худшей ситуации. Быстродействие можно свести к порядку роста.

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

Для оценки скорости роста широко используются обозначения: Тета большое, О большое и Омега большое. Их определения даны здесь.



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

Наши примеры 1-sum, 2-sum и 3-sum просто сформулировать для установления сложности задачи и построения оптимального алгоритма. 1-sum состоит в нахождении числа в массиве. Итак, верхняя граница сложности задачи — специфический алгоритм.

Например, алгоритм перебора, который проверяет каждый элемент массива. Быстродействие равняется O(N). Времени требуется меньше, чем N. Время работы оптимального алгоритма должно быть не выше O(N). Таким образом, конкретный алгоритм устанавливает верхнюю границу времени работы оптимального алгоритма. Но в данном случае легко установить нижнюю границу, которую не преодолеть ни одному алгоритму. Для 1-sum вы должны проверить все элементы массива. Любой пропущенный может оказаться искомым, значит оптимальный алгоритм должен иметь время работы как минимум C*N, то есть Омега(N).

В данном случае верхняя и нижняя границы равны, значит метод перебора оптимален для 1-SUM задачи. Его время работы Тета(N). Он включает Омега(N) и O(N).

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

Метод перебора давал результат О(N^3), но мы его усовершенствовали и получили алгоритм со временем работы O(N^2*log(N)). Это верхняя граница. Нижняя граница: необходимо проверить каждый элемент, чтобы не пропустить искомое, значит время работы оптимального алгоритма — Омега(N). Но никто не знает истинных границ. Верхняя и нижняя граница задачи 3-SUM остаются открытым вопросом. Есть ли оптимальный алгоритм для 3-sum? Мы не знаем.

Мы даже не знаем, есть ли алгоритм со временем работы меньше O(N^2), не знаем верхнюю и нижнюю границы. Это пример нерешённой задачи теории алгоритмов. Нам не известна сложность задачи 3-SUM. Эта методика была успешной в последние десятилетия. Разрабатываем алгоритм, находим нижнюю границу. Если есть разрыв, ищем новый алгоритм, который станет нижней границей, ищем способ повысить нижнюю границу.

Обычно очень сложно находить нижние границы. Тривиальные задачи с перебором элементов не представляют труда. Нетривиальные задачи, например, Объединение-Поиск намного сложнее. В последние десятилетия мы столкнулись с вычислительными сложностями задач при уменьшении верхних границ. Удалось улучшить время работы многих алгоритмов, но остается ещё много нерешенных задач. Это обширное поле для исследования, в котором занято много специалистов.

Есть несколько оговорок. Во-первых, может быть, фокусироваться на худшем случае — слишком пессимистично. У нас есть данные и задачи. Не всегда срабатывает худший вариант. Стоит сосредоточиться на анализе входных данных и поиске алгоритмов, которые эффективны для этих данных.

Во-вторых, для оценки производительности и сравнения алгоритмов потребуется более точный анализ, чем с точностью до постоянного множителя. Мы поговорили о тильда нотации, Тета большое, О большое и Омега большое. В теории алгоритмов имеется огромное количество опубликованных исследований, и многие делают ошибку, интерпретируя результаты поиска улучшенной верхней границы со значением О большое как модель быстродействия. Это ошибка.

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