Алгоритмическая сложность. Алгоритмы поиска

Для любого программиста важно знать основы теории алгоритмов, так как именно эта наука изучает общие характеристики алгоритмов и формальные модели их представления. Ещё с уроков информатики нас учат составлять блок-схемы, что, в последствии, помогает при написании более сложных задач, чем в школе. Также не секрет, что практически всегда существует несколько способов решения той или иной задачи: одни предполагают затратить много времени, другие ресурсов, а третьи помогают лишь приближённо найти решение.

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

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

Определения

Основным показателем сложности алгоритма является время, необходимое для решения задачи и объём требуемой памяти.
Также при анализе сложности для класса задач определяется некоторое число, характеризующее некоторый объём данных – размер входа .
Итак, можем сделать вывод, что сложность алгоритма – функция размера входа.
Сложность алгоритма может быть различной при одном и том же размере входа, но различных входных данных.

Существуют понятия сложности в худшем , среднем или лучшем случае . Обычно, оценивают сложность в худшем случае.

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

Порядок роста сложности алгоритмов

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

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

Виды асимптотических оценок

O – оценка для худшего случая

Рассмотрим сложность f(n) > 0 , функцию того же порядка g(n) > 0 , размер входа n > 0 .
Если f(n) = O(g(n)) и существуют константы c > 0 , n 0 > 0 , то
0 < f(n) < c*g(n),
для n > n 0 .

Функция g(n) в данном случае асимптотически-точная оценка f(n). Если f(n) – функция сложности алгоритма, то порядок сложности определяется как f(n) – O(g(n)).

Данное выражение определяет класс функций, которые растут не быстрее, чем g(n) с точностью до константного множителя.

Примеры асимптотических функций

f(n)	g(n)
2n 2 + 7n - 3	n 2
98n*ln(n)	n*ln(n)
5n + 2	n
8	1

Ω – оценка для лучшего случая

Определение схоже с определением оценки для худшего случая, однако
f(n) = Ω(g(n)) , если
0 < c*g(n) < f(n)

Ω(g(n)) определяет класс функций, которые растут не медленнее, чем функция g(n) с точностью до константного множителя.

Θ – оценка для среднего случая

Стоит лишь упомянуть, что в данном случае функция f(n) при n > n 0 всюду находится между c 1 *g(n) и c 2 *g(n) , где c – константный множитель.
Например, при f(n) = n 2 + n ; g(n) = n 2 .

Критерии оценки сложности алгоритмов

Равномерный весовой критерий (РВК) предполагает, что каждый шаг алгоритма выполняется за одну единицу времени, а ячейка памяти за одну единицу объёма (с точностью до константы).
Логарифмический весовой критерий (ЛВК) учитывает размер операнда, который обрабатывается той или иной операцией и значения, хранимого в ячейке памяти.

Временная сложность при ЛВК определяется значением l(O p) , где O p – величина операнда.
Ёмкостная сложность при ЛВК определяется значением l(M) , где M – величина ячейки памяти.

Пример оценки сложности при вычислении факториала

Необходимо проанализировать сложность алгоритма вычисление факториала. Для этого напишем на псевдокоде языка С данную задачу:

Void main() { int result = 1; int i; const n = ...; for (i = 2; i <= n; i++) result = result * n; }

Временная сложность при равномерном весовом критерии

Достаточно просто определить, что размер входа данной задачи – n .
Количество шагов – (n - 1) .

Таким образом, временная сложность при РВК равна O(n) .

Временная сложность при логарифмическом весовом критерии

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

Итак, в данной задаче выделяется три операции:

1) i <= n

На i-м шаге получится log(n) .
Так как шагов (n-1) , сложность данной операции составит (n-1)*log(n) .

2) i = i + 1

На i-м шаге получится log(i) .
.

3) result = result * i

На i-м шаге получится log((i-1)!) .
Таким образом, получается сумма .

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

Ёмкостная сложность при равномерном весовом критерии

Здесь всё просто. Необходимо подсчитать количество переменных. Если в задаче используются массивы, за переменную считается каждая ячейка массива.
Так как количество переменных не зависит от размера входа, сложность будет равна O(1) .

Ёмкостная сложность при логарифмическом весовом критерии

В данном случае следует учитывать максимальное значение, которое может находиться в ячейке памяти. Если значение не определено (например, при операнде i > 10), то считается, что существует какое-то предельное значение V max .
В данной задаче существует переменная, значение которой не превосходит n (i) , и переменная, значение которой не превышает n! (result) . Таким образом, оценка равна O(log(n!)) .

Выводы

Изучение сложности алгоритмов довольно увлекательная задача. На данный момент анализ простейших алгоритмов входит в учебные планы технических специальностей (если быть точным, обобщённого направления «Информатика и вычислительная техника»), занимающихся информатикой и прикладной математикой в сфере IT.
На основе сложности выделяются разные классы задач: P , NP , NPC . Но это уже не проблема теории асимптотического анализа алгоритмов.

Наверняка вы не раз сталкивались с обозначениями вроде O(log n) или слышали фразы типа «логарифмическая вычислительная сложность» в адрес каких-либо алгоритмов. И если вы так и не понимаете, что это значит, - эта статья для вас.

Оценка сложности

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

Допустим, некоторому алгоритму нужно выполнить 4n 3 + 7n условных операций, чтобы обработать n элементов входных данных. При увеличении n на итоговое время работы будет значительно больше влиять возведение n в куб, чем умножение его на 4 или же прибавление 7n . Тогда говорят, что временная сложность этого алгоритма равна О(n 3) , т. е. зависит от размера входных данных кубически.

Использование заглавной буквы О (или так называемая О-нотация) пришло из математики, где её применяют для сравнения асимптотического поведения функций. Формально O(f(n)) означает, что время работы алгоритма (или объём занимаемой памяти) растёт в зависимости от объёма входных данных не быстрее, чем некоторая константа, умноженная на f(n) .

Примеры

O(n) - линейная сложность

Такой сложностью обладает, например, алгоритм поиска наибольшего элемента в не отсортированном массиве. Нам придётся пройтись по всем n элементам массива, чтобы понять, какой из них максимальный.

O(log n) - логарифмическая сложность

Простейший пример - бинарный поиск. Если массив отсортирован, мы можем проверить, есть ли в нём какое-то конкретное значение, методом деления пополам. Проверим средний элемент, если он больше искомого, то отбросим вторую половину массива - там его точно нет. Если же меньше, то наоборот - отбросим начальную половину. И так будем продолжать делить пополам, в итоге проверим log n элементов.

O(n 2) - квадратичная сложность

Такую сложность имеет, например, алгоритм сортировки вставками. В канонической реализации он представляет из себя два вложенных цикла: один, чтобы проходить по всему массиву, а второй, чтобы находить место очередному элементу в уже отсортированной части. Таким образом, количество операций будет зависеть от размера массива как n * n , т. е. n 2 .

Бывают и другие оценки по сложности, но все они основаны на том же принципе.

Также случается, что время работы алгоритма вообще не зависит от размера входных данных. Тогда сложность обозначают как O(1) . Например, для определения значения третьего элемента массива не нужно ни запоминать элементы, ни проходить по ним сколько-то раз. Всегда нужно просто дождаться в потоке входных данных третий элемент и это будет результатом, на вычисление которого для любого количества данных нужно одно и то же время.

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

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

• Одетым
• Чистым
• Сытым

Какой алгоритм позволит тебе добиться этого результата?

1. Проснуться по будильнику.
2. Принять душ, умыться.
3. Приготовить завтрак, сварить кофе/заварить чай.
4. Поесть.
5. Если не погладил одежду с вечера - погладить.
6. Одеться.
7. Выйти из дома.

Эта последовательность действий точно позволит тебе получить необходимый результат. В программировании вся суть нашей работы заключается в постоянном решении задач. Значительную часть этих задач можно выполнить, используя уже известные алгоритмы. К примеру, перед тобой стоит задача: отсортировать список из 100 имен в массиве . Задача это довольно проста, но решить ее можно разными способами. Вот один из вариантов решения: Алгоритм сортировки имен по алфавиту:

1. Купить или скачать в Интернете “Словарь русских личных имен” 1966 года издания.
2. Находить каждое имя из нашего списка в этом словаре.
3. Записывать на бумажку, на какой странице словаря находится имя.
4. Расставить имена по порядку, используя записи на бумажке.

Позволит ли такая последовательность действий решить нашу задачу? Да, вполне позволит. Будет ли это решение эффективным ? Вряд ли. Здесь мы подошли к еще одному очень важному свойству алгоритмов - их эффективности . Решить задачу можно разными способами. Но и в программировании, и в обычной жизни мы выбираем способ, который будет наиболее эффективным. Если твоя задача - сделать бутерброд со сливочным маслом, ты, конечно, можешь начать с того, что посеешь пшеницу и подоишь корову. Но это будет неэффективное решение - оно займет очень много времени и будет стоить много денег. Для решения твоей простой задачи хлеб и масло можно просто купить. А алгоритм с пшеницей и коровой хоть и позволяет решить задачу, слишком сложный, чтобы применять его на практике. Для оценки сложности алгоритмов в программировании создали специальное обозначение под названием Big-O (“большая О”) . Big-O позволяет оценить, насколько время выполнения алгоритма зависит от переданных в него данных . Давай рассмотрим самый простой пример - передачу данных. Представь, что тебе нужно передать некоторую информацию в виде файла на большое расстояние (например, 5000 километров). Какой алгоритм будет наиболее эффективным? Это зависит от тех данных, с которыми ему предстоит работать. К примеру, у нас есть аудиофайл размером 10 мегабайт.
В этом случае, самым эффективным алгоритмом будет передать файл через Интернет. Это займет максимум пару минут! Итак, давай еще раз озвучим наш алгоритм: “Если требуется передать информацию в виде файлов на расстояние 5000 километров, нужно использовать передачу данных через Интернет”. Отлично. Теперь давай проанализируем его. Решает ли он нашу задачу? В общем-то да, вполне решает. А вот что можно сказать насчет его сложности? Хм, а вот тут уже все интереснее. Дело в том, что наш алгоритм очень сильно зависит от входящих данных, а именно - от размера файлов. Сейчас у нас 10 мегабайт, и все в порядке. А что, если нам нужно будет передать 500 мегабайт? 20 гигабайт? 500 терабайт? 30 петабайт? Перестанет ли наш алгоритм работать? Нет, все эти объемы данных все равно можно передать. Станет ли он выполняться дольше? Да, станет! Теперь нам известна важная особенность нашего алгоритма: чем больше размер данных для передачи, тем дольше времени займет выполнение алгоритма . Но нам хотелось бы более точно понимать, как выглядит эта зависимость (между размером данных и временем на их передачу). В нашем случае сложность алгоритма будет линейной . “Линейная” означает, что при увеличении объема данных время на их передачу вырастет примерно пропорционально. Если данных станет в 2 раза больше, и времени на их передачу понадобится в 2 раза больше. Если данных станет больше в 10 раз, и время передачи увеличится в 10 раз. Используя обозначение Big-O, сложность нашего алгоритма определяется как O(N) . Это обозначение лучше всего запомнить на будущее - оно всегда используется для алгоритмов с линейной сложностью. Обрати внимание: мы вообще не говорим здесь о разных “переменных” вещах: скорости интернета, мощности нашего компьютера и так далее. При оценке сложности алгоритма в этом просто нет смысла - мы в любом случае не можем это контролировать. Big-O оценивает именно сам алгоритм, независимо от “окружающей среды” в которой ему придется работать. Продолжим работать с нашим примером. Допустим, в итоге выяснилось, что размер файлов для передачи составляет 800 терабайт. Если мы будем передавать их через Интернет, задача, конечно, будет решена. Есть только одна проблема: передача по стандартному современному каналу (со скоростью 100 мегабит в секунду), который используется дома у большинства из нас, займет примерно 708 дней. Почти 2 года! :O Так, наш алгоритм тут явно не подходит. Нужно какое-то другое решение! Неожиданно на помощь к нам приходит IT-гигант - компания Amazon! Ее сервис Amazon Snowmobile позволяет загрузить большой объем данных в передвижные хранилища и доставить по нужному адресу на грузовике!
Итак, у нас есть новый алгоритм! “Если требуется передать информацию в виде файлов на расстояние 5000 километров и этот процесс займет больше 14 дней при передаче через Интернет, нужно использовать перевозку данных на грузовике Amazon”. Цифра 14 дней здесь выбрана случайно: допустим, это максимальный срок, который мы можем себе позволить. Давай проанализируем наш алгоритм. Что насчет скорости? Даже если грузовик поедет со скоростью всего 50 км/ч, он преодолеет 5000 километров всего за 100 часов. Это чуть больше четырех дней! Это намного лучше, чем вариант с передачей по интернету. А что со сложностью этого алгоритма? Будет ли она тоже линейной, O(N)? Нет, не будет. Ведь грузовику без разницы, как сильно ты его нагрузишь - он все равно поедет примерно с одной и той же скоростью и приедет в срок. Будет ли у нас 800 терабайт, или в 10 раз больше данных, грузовик все равно доедет до места за 5 дней. Иными словами, у алгоритма доставки данных через грузовик постоянная сложность . “Постоянная” означает, что она не зависит от передаваемых в алгоритм данных. Положи в грузовик флешку на 1Гб - он доедет за 5 дней. Положи туда диски с 800 терабайтами данных - он доедет за 5 дней. При использовании Big-O постоянная сложность обозначается как O(1) . Раз уж мы познакомились с O(N) и O(1) , давай теперь рассмотрим более “программистские” примеры:) Допустим, тебе дан массив из 100 чисел, и задача - вывести в консоль каждое из них. Ты пишешь обычный цикл for , который выполняет эту задачу int numbers = new int [ 100 ] ; // ..заполняем массив числами for (int i: numbers) { System. out. println (i) ; } Какая сложность у написанного алгоритма? Линейная, O(N). Число действий, которые должна совершить программа, зависит от того, сколько именно чисел в нее передали. Если в массиве будет 100 чисел, действий (выводов на экран) будет 100. Если чисел в массиве будет 10000, нужно будет совершить 10000 действий. Можно ли улучшить наш алгоритм? Нет. Нам в любом случае придется совершить N проходов по массиву и выполнить N выводов в консоль. Рассмотрим другой пример. public static void main (String args) { LinkedList< Integer> numbers = new LinkedList < > () ; numbers. add (0 , 20202 ) ; numbers. add (0 , 123 ) ; numbers. add (0 , 8283 ) ; } У нас есть пустой LinkedList , в который мы вставляем несколько чисел. Нам нужно оценить сложность алгоритма вставки одного числа в LinkedList в нашем примере, и как она зависит от числа элементов, находящихся в списке. Ответом будет O(1) - постоянная сложность . Почему? Обрати внимание: каждый раз мы вставляем число в начало списка. К тому же, как ты помнишь, при вставке числа в LinkedList элементы никуда не сдвигаются - происходит переопределение ссылок (если вдруг забыл, как работает LinkedList, загляни в одну из наших ). Если сейчас первое число в нашем списке - число х, а мы вставляем в начало списка число y, все, что для этого нужно: x. previous = y; y. previous = null; y. next = x; Для этого переопределения ссылок нам неважно, сколько чисел сейчас в LinkedList - хоть одно, хоть миллиард. Сложность алгоритма будет постоянной - O(1).

Логарифмическая сложность

Без паники! :) Если при слове “логарифмический” тебе захотелось закрыть лекцию и не читать дальше - подожди пару минут. Никаких математических сложностей здесь не будет (таких объяснений полно и в других местах), а все примеры разберем “на пальцах”. Представь, что твоя задача - найти одно конкретное число в массиве из 100 чисел. Точнее, проверить, есть ли оно там вообще. Как только нужное число найдено, поиск нужно прекратить, а в консоль вывести запись “Нужное число обнаружено! Его индекс в массиве = ....” Как бы ты решил такую задачу? Здесь решение очевидно: нужно перебрать элементы массива по очереди начиная с первого (или с последнего) и проверять, совпадает ли текущее число с искомым. Соответственно, количество действий прямо зависит от числа элементов в массиве. Если у нас 100 чисел, значит, нам нужно 100 раз перейти к следующему элементу и 100 раз проверить число на совпадение. Если чисел будет 1000, значит и шагов-проверок будет 1000. Это очевидно линейная сложность, O(N) . А теперь мы добавим в наш пример одно уточнение: массив, в котором тебе нужно найти число, отсортирован по возрастанию . Меняет ли это что-то для нашей задачи? Мы по-прежнему можем искать нужное число перебором. Но вместо этого мы можем использовать известный алгоритм двоичного поиска .
В верхнем ряду на изображении мы видим отсортированный массив. В нем нам необходимо найти число 23. Вместо того, чтобы перебирать числа, мы просто делим массив на 2 части и проверяем среднее число в массиве. Находим число, которое располагается в ячейке 4 и проверяем его (второй ряд на картинке). Это число равно 16, а мы ищем 23. Текущее число меньше. Что это означает? Что все предыдущие числа (которые расположены до числа 16) можно не проверять : они точно будут меньше того, которое мы ищем, ведь наш массив отсортирован! Продолжим поиск среди оставшихся 5 элементов. Обрати внимание: мы сделали всего одну проверку, но уже отмели половину возможных вариантов. У нас осталось всего 5 элементов. Мы повторим наш шаг - снова разделим оставшийся массив на 2 и снова возьмем средний элемент (строка 3 на рисунке). Это число 56, и оно больше того, которое мы ищем. Что это означает? Что мы отметаем еще 3 варианта - само число 56, и два числа после него (они точно больше 23, ведь массив отсортирован). У нас осталось всего 2 числа для проверки (последний ряд на рисунке) - числа с индексами массива 5 и 6. Проверяем первое из них, и это то что мы искали - число 23! Его индекс = 5! Давай рассмотрим результаты работы нашего алгоритма, а потом разберемся с его сложностью. (Кстати, теперь ты понимаешь, почему его называют двоичным: его суть заключается в постоянном делении данных на 2). Результат впечатляет! Если бы мы искали нужное число линейным поиском, нам понадобилось бы 10 проверок, а с двоичным поиском мы уложились в 3! В худшем случае их было бы 4, если бы на последнем шаге нужным нам числом оказалось второе, а не первое. А что с его сложностью? Это очень интересный момент:) Алгоритм двоичного поиска гораздо меньше зависит от числа элементов в массиве, чем алгоритм линейного поиска (то есть, простого перебора). При 10 элементах в массиве линейному поиску понадобится максимум 10 проверок, а двоичному - максимум 4 проверки. Разница в 2,5 раза. Но для массива в 1000 элементов линейному поиску понадобится 1000 проверок, а двоичному - всего 10 ! Разница уже в 100 раз! Обрати внимание: число элементов в массиве увеличилось в 100 раз (с 10 до 1000), а количество необходимых проверок для двоичного поиска увеличилось всего в 2,5 раза - с 4 до 10. Если мы дойдем до 10000 элементов , разница будет еще более впечатляющей: 10000 проверок для линейного поиска, и всего 14 проверок для двоичного. И снова: число элементов увеличилось в 1000 раз (с 10 до 10000), а число проверок увеличилось всего в 3,5 раза (с 4 до 14). Сложность алгоритма двоичного поиска логарифмическая , или,если использовать обозначения Big-O, - O(log n) . Почему она так называется? Логарифм - это такая штуковина, обратная возведению в степень. Двоичный логарифм использует для подсчета степени числа 2. Вот, например, у нас есть 10000 элементов, которые нам надо перебрать двоичным поиском.
Сейчас у тебя есть картинка перед глазами, и ты знаешь что для этого нужно максимум 14 проверок. Но что если картинки перед глазами не будет, а тебе нужно посчитать точное число необходимых проверок? Достаточно ответить на простой вопрос: в какую степень надо возвести число 2, чтобы полученный результат был >= числу проверяемых элементов? Для 10000 это будет 14 степень. 2 в 13 степени - это слишком мало (8192) А вот 2 в 14 степени = 16384 , это число удовлетворяет нашему условию (оно >= числу элементов в массиве). Мы нашли логарифм - 14. Столько проверок нам и нужно! :) Алгоритмы и их сложность - тема слишком обширная, чтобы вместить ее в одну лекцию. Но знать ее очень важно: на многих собеседованиях ты получишь алгоритмические задачи. Для теории я могу порекомендовать тебе несколько книг. Начать можно с “видео про Big-O на YouTube. Увидимся на следующих лекциях! :)

Определение сложности алгоритма

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

Следует иметь в виду, что существует несколько оценок сложности алгоритма.

Асимптотика функции трудоемкости - это операционная сложность. Кроме нее можно указать следующие виды сложностей.

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

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

Структурная сложность - характеристика количества управляющих структур в алгоритме и специфики их взаиморасположения.

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

Виды и обозначения асимптотик

В асимптотическом анализе алгоритмов принято использовать обозначения математического асимптотического анализа. При этом рассматриваются три оценки (асимптотики) трудоемкости алгоритмов , которые обозначаются так:

• 1) /(я) = О^(п)) - асимптотически точная оценка функции трудоемкости /(«), или операционная сложность алгоритма;
• 2) /(п) = 0{§{п)) - асимптотически точная верхняя оценка функции трудоемкости /(п );
• 3) /(л) = ?2(#(л)) - асимптотически точная нижняя оценка функции трудоемкости /(п).

Вместо обозначения С1^(п)) очень часто используется более простое о(^(«)) с буквой «о» строчное курсивное.

Поясним семантику формул на примере: если записано /(я) = 0(^2(л)), ТО ЭТО означает, ЧТО функция g(n)=og 2 (n) является асимптотически точной оценкой функции трудоемкости /(«). По сути дела имеет место двухпозиционное определение в форме утверждения:

Если f(n) = @(log 2 («)),

mo g(n) = log 2 (л) - асимптотически точная оценка f(n).

Заметим, что постоянный множитель не влияет на порядок сложности алгоритма, поэтому основание логарифма опускают при указании логарифмической трудоемкости, и пишут просто /(л) = @(1о§(л)), подразумевая у логарифма произвольное основание большее единицы.

Формальные определения асимптотик

Асимптотически точная оценка функции трудоемкости с, с 2 , л 0 , такие что при л>л 0 функция /(л) с точностью до постоянных множителей не отличается от функции g(л), то функция g(n) называется асимптотически точной оценкой функции /(л).

• 3 с ] , с 2 е Ж, с х > 0, с 2 > 0:
  • (3 л 0 е К, л 0 > 0: (/л е К, л > л 0:0 g(n) /(л) = 0(?(л)),

где 9^, N - множества всех вещественных и натуральных чисел соответственно.

Асимптотически точная верхняя оценка функции трудоемкости вербально определяется так: если существуют положительные числа с и л 0 , такие что при л>л 0 функция /(л) растет не быстрее, чем функция g(n) с точностью до постоянного множителя с, то функция g{n) называется асимптотически точной верхней оценкой функции Ап).

Более точная формальная запись определения имеет вид:

• 3 с е % с > 0:
  • (3 л 0 е X, л 0 > 0: (/л е К, л > л 0:0 с? #(л))) 0(g(n))

Асимптотически точная нижняя оценка функции трудоемкости вербально определяется так: если существуют положительные числа с и л 0 , такие что при л>л 0 функция /(л) растет не медленнее, чем функция g{n) с точностью до постоянного множителя с, то функция?(л) называется асимптотически точной нижней оценкой функции

Более точная формальная запись определения имеет вид:

• 3 с е 9^, с > 0:
  • (3 я 0 е X, я 0 > 0: (/я е К, я > я 0: 0 с? g(n)

/(я) = 0.^(п))

Заметим, следующее:

• 1) неравенствам, указанным в формальных определениях асимптотик, в общем случае может удовлетворять не одна, а некоторое множество функций, часто с бесчисленным множеством членов, поэтому конструкции Q(g(n )), 0^{п)) и 0.^(п)) символизируют множества функций , с которыми сопоставляется исследуемая функция трудоемкости /(я); в силу этого в обозначениях асимптотик вида /(я) = 0(?(я)), /(/0 = О(? тах (л)), Дя) = ?2(? т1п (я)) вместо знака «=» рациональнее было бы использовать знак «е»;
• 2) конструкции (д^{п )), 0^{п)) и ?1^{п)), использованные в качестве обозначений некоторых величин, следует читать соответственно так: любая функция, совпадающая, растущая не быстрее и растущая не медленнее g{n).

Совпадение и различие асимптотик

Обратим внимание на следующий факт: оценка /(я) = 0(?(я)) устанавливает для /(я) одновременно и верхнюю, и нижнюю оценки, поскольку ее определение предполагает справедливость отношения с г g(n)

Достаточно очевидно следующее свойство асимптотик: если оценка ф(п) = ©^(п)) существует, то справедливы равенства /(п ) = 0(^(я)) и /(я) = ?2(#(я)), т.е. верхние и нижние оценки трудоемкости совпадают друг с другом; если же /(я) = 0(? тах (я)) и ф(п) = С1^ тт (п )), и g max (n)фg m 1п (я), то не существует функции g(n), такой что /(я) = 0(?(я)).

Совпадение верхней и нижней оценок трудоемкости возможно в следующих случаях:

• 1) функция трудоемкости при всех значениях длины входа является детерминированной (неслучайной) функцией, т.е. количество выполняемых операций не зависит от конкретики значений исходных данных; таковыми, например, являются функции зависимостей количества операций умножения и деления от числа неизвестных величин в алгоритме решения систем линейных алгебраических уравнений методом ИЗ-разложения;
• 2) функция трудоемкости является случайной функцией, т.е. количество выполняемых операций зависит от конкретики исходных данных и (или) порядка их поступления, и можно указать функции / т|п (я), / тах (я), описывающие минимальное и максимальное количество операций, выполняемых исполнителем алгоритма при конкретной длине входа я, однако обе эти функции имеют одинаковые доминанты, - например, являются полиномами одного и того же порядка.

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

• 1) постоянные множители не имеют значения для определения порядка сложности, т.е. 0(к? g(n )) = 0(g(«)) ;
• 2) порядок сложности произведения двух функций равен произведению их сложностей, поскольку справедливо равенство:
• 0(gl (я) §2 (я)) = 0 (?| (я)) 0 (#2(я)) ;
• 3) порядок сложности суммы функций равен порядку доминанты слагаемых, например: 0(я э +п 2 +п) = 0(я 5).

В приведенных правилах использован символ только одной асимптотики 0(»), но они справедливы для всех асимптотических оценок - и для 0( ) , и &.{ ).

Во множестве элементарных функций можно указать список функционального доминирования: если -переменная, a,b - числовые константы, то справедливы следующие утверждения: я" доминирует я!; я! доминирует а"; а" доминирует Zj", если а>Ь а п доминирует п ь, если а > 1 при любом b е 9? ; п а доминирует а/, если а>Ь я доминирует log д (я), если а > 1.

Оценивание средней трудоемкости

В практике реальных вычислений существенный интерес представляет оценка /(я) математического ожидания трудоемкости М, поскольку в подавляющем большинстве случаев /(я) является случайной функцией. Однако в процессе экспериментальных исследований алгоритмов со случайной /(я) возникает дополнительная проблема - выбора количества испытаний для надежной оценки М. Преодоление этой проблемы является центральной задачей в . Предлагаемое в решение основано на использовании бета-распределения для аппроксимации /(я). Это весьма конструктивная и универсальная методика. Однако в современных условиях, когда производительность ЭВМ достаточно высока, во многих случаях можно использовать более простой способ выбора объема испытаний, основанный на контроле текущей вариативности значений f(n) - значения оцениваются до тех пор, пока вариативность оценок не станет меньше заданной погрешности.

Оценивание операционной сложности алгоритма

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

Рассмотрим алгоритм удаления к -го элемента из массива размером п , состоящий из перемещения элементов массива от (к + 1) -го до п -го на одну позицию назад к началу массива и уменьшения числа элементов п на единицу. Сложность цикла обработки массива составляет О(п-к), так как тело цикла (операция перемещения) выполняется п-к раз, а сложность тела цикла равна 0(1), т.е. является константой.

В рассматриваемом примере сложность охарактеризована асимптотикой 0(»), поскольку количество выполняемых операций в этом алгоритме не зависит от конкретики значений данных. Функция трудоемкости является детерминированной, и все виды асимптотик совпадают друг с другом: f(n) = Q(n-k), f(n) = 0(n-k) и f(n) = Q(n- к ). Об этом факте и свидетельствует указание именно ©( ). Использовать 0(*) и/или?2(*) следует только в том случае, если эти асимптотики различаются.

Тип цикла (for, while, repeat) не влияет на сложность. Если один цикл вложен в другой и оба цикла зависят от размера одной и той же переменной, то вся конструкция характеризуется квадратичной сложностью. Вложенность повторений является основным фактором роста сложности. В качестве примера приведем сложности хорошо известных алгоритмов поиска и сортировки для массива размером п:

• число операций сравнения в последовательном поиске: 0(я);
• число операций сравнения в бинарном поиске: 0(log 2 п );
• число операций сравнения в методе простого обмена (пузырьковая сортировка): 0(я 2);
• число операций перестановки в пузырьковой сортировке: 0{п 2);

Заметим, что число операций сравнения в методе простого обмена имеют асимптотику 0(п 2), а число операций перестановки имеет две различных асимптотики 0(п 2) и?2(0), потому что количество сравнений не зависит от конкретики значений сортируемых данных, в то время как количество перестановок определяется именно этой конкретикой. Перестановки могут не осуществляться вовсе, - если массив данных правильно упорядочен изначально, либо количество перестановок может быть максимальным - порядка п 2 , - если сортируемый массив исходно упорядочен в противном направлении.

Название функции g(n) в асимптотиках /(л) = @(^(л)) и /(«) = 0(g(n)) функции трудоемкости /(«) используется для характеристики алгоритма. Таким образом, говорят об алгоритмах полиномиальной, экспоненциальной, логарифмической и т. д. сложности.

Функция сложности 0(1). В алгоритмах константной сложности большинство операций в программе выполняются один или несколько раз. Любой алгоритм, всегда требующий (независимо от размера данных) одного и того же времени, имеет константную сложность.

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

Функция сложности 0(N 2), 0(N 3), 0(№) - полиномиальная функция сложности: число операций растет пропорционально квадрату N. В общем случае может быть О(Л^) в зависимости от сложности задачи. Эта функция сложности характеризует сложный цикл.

Функция сложности O(Log 2 (A0), 0(N log 2 (A0). Такое время работают алгоритмы, которые делят большую проблему на множество небольших, а затем, решив их, объединяют решения.

Функция сложности 0(e N). Алгоритмы с экспоненциальной сложностью чаще всего возникают в результате подхода, именуемого методом грубой силы.

Функция сложности 0(М) - число операций растет пропорционально факториалу N.

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

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

Например, рассмотрим алгоритм обработки элементов массива.

For /": = 1 to N do Begin

Сложность этого алгоритма О (А), так как тело цикла выполняется А раз, и сложность тела цикла равна 0(1). Если один цикл вложен в другой и оба цикла зависят от размера одной и той же переменной, то вся конструкция характеризуется квадратичной сложностью.

For /: = 1 to N do For j: = 1 to N do Begin

Сложность этой программы 0(N 2).

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

• - ввод массива (надо прочесть А элементов);
• - поиск наибольшего элемента (надо сделать А - 1 сравнение);
• - вывод результата (надо вывести одно число или строку).

Сложим число операций А + (А - 1) + 1 = 2А, т.е. существует

такая константа, что при любом А число операций не превышает СА. Следовательно, сложность алгоритма равна 0(A).

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

• - ввод массива (Аопераций ввода);
• - поиск элемента с заданным свойством (элемент может находиться как ближе к началу массива, так и в самом конце; если элемента не существует, то необходимо сделать все А сравнений, чтобы в этом убедиться);
• - вывод результата.

В лучшем случае указанный алгоритм потребует А + 2 операции (ввод всего массива, единственное сравнение, вывод), в худшем (когда такого элемента нет, 2А + 1 операцию). Если А будет большим числом, к примеру порядка 10 6 , то единицей можно пренебречь. Следовательно, сложность алгоритма равна 0(N).

Пример 3. Определим функцию сложности алгоритма шифрования слова длиной L методом подстановки. Пусть существует таблица, в которой для каждого символа алфавита записан символ, на который его надо заменить. Обозначим число букв алфавита S. Алгоритм состоит из следующих шагов:

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

Общее число операций 1 + (S +)L. В случае достаточно больших S и L единицами можно пренебречь, и получится, что функция сложности приведенного алгоритма есть O(S L).

Пример 4. Определим функцию сложности алгоритма перевода натурального числа 1 V в двоичную систему счисления (без операций ввода и вывода данных). Алгоритм состоит из следующих шагов:

• - цикл, пока результат деления числа на 2 не станет равным 0:
• - разделить число на 2 и запомнить остаток;
• - принять результат деления за новое число;
• - конец цикла.

Общее число операций не превышает 1 + log 2 A. Поэтому описанный алгоритм имеет сложность 0(og 2 N).