Обозначение	Интуитивное объяснение	Определение
	f ограничена сверху функцией g	style="max-width: 98%; height: auto; width: auto;" src="/pictures/wiki/files/101/eebfe73c29ff3f9bc886d263bd3e91f3.png" border="0"> или style="max-width: 98%; height: auto; width: auto;" src="/pictures/wiki/files/100/d96907f9d7419a7e0c74e4089c35c35e.png" border="0">
	f ограничена снизу функцией g (с точностью до постоянного множителя) асимптотически	style="max-width: 98%; height: auto; width: auto;" src="/pictures/wiki/files/48/0fda981f377ae7b8d361f58ce148c173.png" border="0">
	f ограничена снизу и сверху функцией g асимптотически	0), n_0: \forall (n>n_0) \; |Cg(n)|
	g доминирует над f асимптотически	style="max-width: 98%; height: auto; width: auto;" src="/pictures/wiki/files/49/176ce786e936badb831a0bb87f25249d.png" border="0">
	f доминирует над g асимптотически	style="max-width: 98%; height: auto; width: auto;" src="/pictures/wiki/files/53/554bc3f42cfa6d0638722e58e4a99d8b.png" border="0">
	f эквивалентна g асимптотически

Примеры

Замечания

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

Если решение некоторой задачи для n-вершинного графа при одном алгоритме занимает время (число шагов) порядка n C , а при другом - порядка n+n!/C, где C - постоянное число, то согласно «полиномиальной идеологии» первый алгоритм практически эффективен, а второй - нет, хотя, например, при С=10 (10 10) дело обстоит как раз наоборот.

1. Эффективные, но сложные алгоритмы могут быть нежелательными, если готовые программы будут поддерживать лица, не участвующие в написании этих программ. Будем надеяться, что принципиальные моменты технологии создания эффективных алгоритмов широко известны, и достаточно сложные алгоритмы свободно применяются на практике. Однако необходимо предусмотреть возможность того, что эффективные, но «хитрые» алгоритмы не будут востребованы из-за их сложности и трудностей, возникающих при попытке в них разобраться.
2. Известно несколько примеров, когда эффективные алгоритмы требуют таких больших объемов машинной памяти (без возможности использования более медленных внешних средств хранения), что этот фактор сводит на нет преимущество «эффективности» алгоритма.
3. В численных алгоритмах точность и устойчивость алгоритмов не менее важны, чем их временная эффективность.

Классы сложности

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

Класс P

Проблема равенства классов P и NP

Знаменитые ученые

• Леонид Левин
• Александр Разборов
• Эди Шеймир

См. также

Ссылки

• Юрий Лифшиц «Современные задачи теоретической информатики » . Курс лекций по алгоритмам для NP-трудных задач.
• А. А. Разборов Theoretical Computer Science: взгляд математика // Компьютерра . - 2001. - № 2. (альтернативная ссылка)
• А. А. Разборов О сложности вычислений // Математическое просвещение . - МЦНМО , 1999. - № 3. - С. 127-141.

Wikimedia Foundation . 2010 .

Смотреть что такое "Временная сложность алгоритма" в других словарях:

временная сложность (алгоритма) - — Тематики защита информации EN time complexity … Справочник технического переводчика

СЛОЖНОСТЬ ОПЕРАТОРСКОЙ ДЕЯТЕЛЬНОСТИ - совокупность объективных факторов, влияющих на качество и продолжительность выполнения человеком требуемых функций в СЧМ. С. о. д. разделяется на несколько видов, каждый из которых характеризуется совокупностью факторов, определенным образом… … Энциклопедический словарь по психологии и педагогике

Вычислений функция, дающая числовую оценку трудности (громоздкости) процессов применения алгоритма к исходным данным. Уточнением А. с. вычислений служит понятие сигнализирующей функции (или просто сигнализирующей) функции, к рая задается… … Математическая энциклопедия

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

В информатике, теория сложности вычислений является разделом теории вычислений, изучающим стоимость работы, требуемой для решения вычислительной проблемы. Стоимость обычно измеряется абстрактными понятиями времени и пространства, называемыми… … Википедия

Это алгоритм для упорядочения элементов в списке. В случае, когда элемент списка имеет несколько полей, поле, служащее критерием порядка, называется ключом сортировки. На практике в качестве ключа часто выступает число, а в остальных полях… … Википедия

Алгоритм сортировки это алгоритм для упорядочения элементов в списке. В случае, когда элемент списка имеет несколько полей, поле, служащее критерием порядка, называется ключом сортировки. На практике в качестве ключа часто выступает число, а в… … Википедия

- (GM) криптографическая система с открытым ключом, разработанная Шафи Голдвассером и Сильвио Микали в 1982 году. GM является первой схемой вероятностного шифрования с открытым ключом, доказуемо стойкая при стандартных криптографических… … Википедия Подробнее

Привет! Сегодняшняя лекция будет немного отличаться от остальных. Отличаться она будет тем, что имеет лишь косвенное отношение к 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. Увидимся на следующих лекциях! :)

Для решения одной и той же задачи часто можно придумать более одного алгоритма. В связи с чем, возникает вопрос: какой из алгоритмов “лучше”?

В большинстве случаев, “лучше”, видимо, такой алгоритм, который на тех же входных данных приходит к решению задачи, потребляя меньшее количество вычислительных ресурсов (памяти и времени). Это, конечно, нестрогое рассуждение. Для более строгого рассуждения введем несколько понятий.

Вычислительный процесс алгоритма это последовательность шагов, пройденная при исполнении алгоритма для некоторых входных данных.

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

Временна́я сложность алгоритма это время \(T\) , необходимое для завершения вычислительного процесса алгоритма для некоторых входных данных.

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

Однако можно время \(T\) выразить через количество элементарных действий \(k\) и среднее время выполнения элементарного действия \(t\) :

При этом, \(k\) является свойством самого алгоритма, а \(t\) – свойством исполнителя.

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

Порядок роста положительно-определенная функция \(g(x)\) имеет порядок роста \(f(x)\) (записывается \(g(x)=\mathcal{O}(f(x))\) ), если \(\exists c>0: \: \forall x>x_0, \, g(x) \leq c f(x)\) .

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

Так, например, чтение данных и сохранение их в памяти в виде массива будет иметь сложность \(\mathcal{O}(n)\) , или линейную сложность , а умножение матриц уже кубическую \(\mathcal{O}(n^3)\) .

Кроме времмено́й сложности алгоритма, важной оказывается так же пространственная сложность алгоритма.

Пространственная сложность алгоритма это количество дополнительной памяти \(S\) , которое алгоритм требует для работы. Память \(D\) , необходимая для хранения входных данных, не включается в \(S\) .

\(S\) в общем случае тоже зависит от исполнительного устройства. Скажем, если два исполнительных устройства поддерживают целые длинной 4 и 8 байт соответственно, то пространственная сложность алгоритма на 8-байтных целых будет вдвое больше, чем на 4-байтных целых. Поэтому пространственная сложность оценивается так же порядком роста.

Классы сложности алгоритмов

Выделяются определенные классы сложности : это категории, которые имеют схожую сложность.

Выделяют следующие основные классы сложности:

DTIME Машина Тьюринга находит решение задачи за конечное время (количество шагов). Часто уточняется асимптотика алгоритма, так, скажем, если порядок роста времени работы \(T(n) = \mathcal{O}(f(n))\) , то указывают \(DTIME(f(n))\) . P Машина Тьюринга находит решение задачи за полиномиальное время (количество шагов), т.е. \(T(n) = \mathcal{O}(n^k)\) , где \(k\in \mathbb{N}\) . \(P=DTIME(n^k)\) EXPTIME Машина Тьюринга находит решение задачи за экспоненциальное время (количество шагов), т.е. \(T(n) = \mathcal{O}(2^{n^k})\) , где \(k\in \mathbb{N}\) . \(EXPTIME=DTIME(2^{n^k})\) . DSPACE Машина Тьюринга находит решение задачи, используя конечное количество дополнительной памяти (ячеек). Часто уточняется асимптотика алгоритма, так, скажем, если порядок роста потребления памяти \(S(n) = \mathcal{O}(f(n))\) , то указывают \(DSPACE(f(n))\) . L Машина Тьюринга находит решение задачи c логарифмической пространственной сложностью, то есть \(S(n) = \mathcal{O}(\log n)\) . \(L=DSPACE(\log n)\) . PSPACE Машина Тьюринга находит решение задачи c полиномиальной пространственной сложностью, то есть \(S(n) = \mathcal{O}(n^k)\) , где \(k\in \mathbb{N}\) . \(PSPACE=DSPACE(n^k)\) . EXPSPACE Машина Тьюринга находит решение задачи c экспоненциальной пространственной сложностью, то есть \(S(n) = \mathcal{O}(2^{n^k})\) , где \(k\in \mathbb{N}\) . \(EXPSPACE=DSPACE(2^{n^k})\) .

Кроме того, существуют теоретические классы сложности, которые оперируют понятием недетерменированной машины Тьюринга (НМТ). Их определения совпадают с вышеприведенными, с заменой машины Тьюринга на НМТ, а названия имеют префикс N (например NP), кроме NTIME и NSPACE, где D заменяется на N.

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

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

Известно, что \(P \subseteq NP \subseteq PSPACE \subseteq EXPTIME \subseteq NEXPTIME \subseteq EXPSPACE\)

Кроме того, \(P \subsetneq EXPTIME\) , \(NP \subsetneq NEXPTIME\) , \(PSPACE \subsetneq EXPSPACE\)

Так же известно, что если \(P = NP\) , то \(EXPTIME = NEXPTIME\) .

Вопрос равенства P и NP является одним из главных нерешенных вопросов современной информатики.

Примеры алгоритмов

Приведем несколько примеров простых алгоритмов и рассмотрим их сложность.

Возведение в целую степень

Этот алгоритм был описан в Древней Индии еще до нашей эры и используется для вычисления натуральной степени \(n\) вещественного числа \(x\)

1. Записать \(n\) в двоичной системе счисления
2. Заменить в этой записи каждую из 1 парой букв КХ, а каждый 0 – буквой К
3. Вычеркнуть крайнюю левую пару КХ
4. Читая полученную строку слева направо, встречая букву К возвести результат в квадрат, а встречая букву X – умножить результат на x. В начале результат равен x.

В этом алгоритме, мы имеем число операций умножения, равное количеству цифр в двоичном представлении \(n\) в лучшем случае, и \(2(n-1)\) в худшем случае. В любом случае, временная сложность .

Дополнительной памяти в эффективной реализации алгоритма практически не требуется, и она не зависит от входных данных, поэтому пространственная сложность \(S(n) = \mathcal{O}(1)\) .

Следует заметить, что существуют более эффективные алгоритмы. Однако по сравнению с “наивной” реализацией, требующей \(\mathcal{O}(n)\) операций умножения, этот алгоритм сравнительно эффективен.

Умножение целых

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

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

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

Поскольку целочисленное деление и умножение на 2 можно реализовать сдвигом, этот алгоритм дает \(2 \log_2 n\) операций сдвига, где \(n\) – меньшее из двух чисел. В худшем случае так же получается \(\log_2 n - 1\) операций сложения. В любом случае, временная сложность \(T(n) = \mathcal{O}(\log n)\) .

Для эффективной реализации алгоритма, дополнительной памяти практически не требуется, и она не зависит от входных данных, поэтому \(S(n) = \mathcal{O}(1)\)

Опять же, следует заметить, что существуют более эффективные алгоритмы. Однако по сравнению с “наивной” реализацией, требующей \(\mathcal{O}(n)\) операций сложения, этот алгоритм сравнительно эффективен.

Пример

Умножение 23 на 43.

Возьмем 23 в качестве второго множителя.

43	23	нечетное
86	11	нечетное
172	5	нечетное
344	2
688	1	нечетное

Результат \(43+86+172+688 = 989\)

Получили 10 операций сдвига и 4 операции сложения. Для справки, \(\log_2(23) \approx 4.52\) .

Функция сложности 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).

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

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

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

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

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

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

Function Factorial(x:Integer): Integer;

Var m,i: Integer;

For i:=2 To x Do m:=ro*i;

Подсчитаем общее число операций, выполняемых программой при данном значении x. Один раз выполняется оператор m:=1; тело цикла (в котором две операции: умножение и присваивание) выполняется х - 1 раз; один раз выполняется присваивание Factorial:=m. Если каждую из операций принять за единицу сложности, то временная сложность всего алгоритма будет 1 + 2 (x - 1) + 1 = 2х Отсюда понятно, что в качестве параметра следует принять значение х. Функция временной сложности получилась следующей:

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

Пример 2. Вычисление скалярного произведения двух векторов А = (a1, a2, …, ak), В = (b1, b2, …, bk).

For i:=l To k Do AB:=AB+A[i]*B[i];

В этой задаче объем входных данных п = 2k. Количество выполняемых операций 1 + 3k = 1 + 3(n/2). Здесь можно взять V= k= п/2. Зависимости сложности алгоритма от значений элементов векторов А и В нет. Как и в предыдущем примере, здесь можно говорить о линейной зависимости временной сложности от параметра данных.

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

Вторая проблема связана с классификацией алгоритмов по временной сложности. Функция Tα(V) обычно растет с ростом V. Как быстро она растет? Существуют алгоритмы с линейной зависимостью Тα от V (как это было в рассмотренных нами примерах), с квадратичной зависимостью и с зависимостью более высоких степеней. Такие алгоритмы называются полиномиальными. А существуют алгоритмы, сложность которых растет быстрее любого полинома. Проблема, которую часто решают теоретики - исследователи алгоритмов, заключается в следующем вопросе: возможен ли для данной задачи полиномиальный алгоритм?

Функции, часто встречающиеся при анализе алгоритмов:

• log n (логарифмическое время),
• n (линейное время),
• n log n ,
• n 2 (квадратичное время),
• 2 n (экспоненциальное время).

Первые четыре функции имеют невысокую скорость роста и алгоритмы, время работы которых оценивается этими функциями, можно считать быстродействующими. Скорость роста экспоненциальной функции иногда характеризуют как «взрывную». Для сравнения допустим, что имеются алгоритмы, трудоемкость которых (число операций) достаточно точно отражается этими функциями. Пусть эти алгоритмы выполняются на компьютере, работающем со скоростью 10 12 операций в секунду. При длине входа n ≤ 100000 алгоритмы, скорость работы которых оценивается первыми четырьмя функциями, получат ответ за ничтожные доли секунды. Для алгоритма с трудоемкостью 2 n время работы оценивается следующим образом:

• n = 50 ≈ 19 минут,
• n = 60 ≈ 320 часов,
• n = 70 ≈ 37 лет.

Вопрос 15=49. Последовательные, циклические и рекурсивные алгоритмы.

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

Пример. Вычислить периметр треугольника со сторонами a,b,c.13

Алгоритм разветвляющейся структуры

На практике редко удается представить решение задачи в виде алгоритма

линейной структуры. Часто в зависимости от каких-либо промежуточных

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

формулам, т.е. в зависимости от выполнения некоторого логического условия

вычислительный процесс осуществляется по одной или другой формуле.

Алгоритм такого вычислительного процесса называется алгоритмом

разветвляющейся структуры.

Ветвление - управляющая структура, организующая выполнение лишь

одного из двух указанных действий в зависимости от справедливости

некоторого условия.

Условие - вопрос, имеющий два варианта ответа: да или нет.

Запись ветвления выполняется в двух формах: полной и неполной (Рис. 1 а, б).

а) полная форма б) неполная форма

Циклические алгоритмы – алгоритмы, в которых приходится многократно вычислять значения по одним и тем же математическим зависимостям (блок схемам) для различных значений входящих в них величин. Использование циклов позволяет существенно сократить объем схемы

алгоритма и длину соответствующей ей программы. Различают циклы с

заданным и неизвестным числом повторений. С заданным числом повторений -

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

цикл с постусловием.

Функция (или процедура), которая прямо или косвенно обращается к себе, называется рекурсивной. Рекурсия - метод определения функции через её предыдущие и ранее определенные значения, а так же способ

организации вычислений, при котором функция вызывает сама себя с другим аргументом

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

решение получается достаточно легко. Далее "обратный ход" дает последовательные решения для задачи все большего размера, вплоть до первоначального. В основе реализации процедуры с рекурсией лежит стек (память "магазинного" типа), где хранятся данные, участвующие во всех вызовах процедуры, при которых она еще не завершила свою работу. Рекурсия – это способ организации процесса вычисления, когда алгоритм обращается сам к себе. Принцип рекурсии позволяет решить сложную задачу путем последовательного решения более простых подзадач.Как правило, рекурсия необходима в тех случаях, когда требуется перебрать слишком много вариантов. Рекурсию принято считать как одну из разновидностей циклического алгоритма. Рекурсивная форма организации позволяет придать алгоритму более компактный вид. Таким образом, решается проблема от сложного к простому – содержание рекурсивного алгоритма отражает более сложный объект через более простой такого же типа. Обычно рекурсивный алгоритм содержит следующие основные части:

– условие для завершения цикла;

– тело рекурсии, которое включает действия, предназначенные для

выполнения на каждой итерации;

– шаг рекурсии, на котором рекурсивный алгоритм вызывает сам себя.

Различают прямую и косвенную рекурсию. В первом случае алгоритм

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

называется косвенно рекурсивной.

Основное требование к рекурсивным алгоритмам – процесс обращения не

должен быть бесконечным. Другими словами, должна быть реализована

проверка завершения вызова, или в рекурсивном определении должно

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

рекурсии прекращается.

Примером рекурсивной функции является вычисление факториала числа.

int factoria(int n)

if (n) return n* factoria(n-1);

else return 1;

Пример рекурсивной процедуры:

procedure Rec(a: integer); begin if a>0 then Rec(a-1); writeln(a); end;

Рассмотрим, что произойдет, если в основной программе поставить вызов, например, вида Rec(3). Ниже представлена блок-схема, показывающая последовательность выполнения операторов.