ОЦЕНКА СЛОЖНОСТИ АЛГОРИТМОВ СОРТИРОВКИ
В первую очередь алгоритмы сортировки характеризуются емкостной сложностью, отражающей, объем памяти ЭВМ, необходимый для хранения дополнительных переменных. Объем памяти, необходимый для хранения сортируемой последовательности, одинаков для всех алгоритмов, поэтому в анализе не учитывается.
Производительность алгоритмов сортировки целесообразно оценивать по их быстродействию, т.е. по временной сложности. В свою очередь временная сложность определяется, главным образом, числом операций, выполняемых в процессе реализации алгоритма, поэтому обычно ограничиваются оценками операционной сложности. В то же время практический интерес чаще всего представляют не асимптотические, а фактические оценки трудоемкости алгоритмов при реальных значениях длины входа п , а не при п —> °°.
Поэтому традиционной мерой трудоемкости сортировок являются средние количества необходимых сравнений ключей (С) и число пересылок или перестановок элементов (Р), рассматриваемые как функции числа п сортируемых элементов. Хорошие алгоритмы сортировки требуют порядка п • ^2(я) сравнений, а простые — порядка п 2 сравнений и эффективны только при малых значениях длины входа.
Big O Notation: что это такое и как её посчитать
Software Engineer Валерий Жила подробно рассказал, что такое O(n), и показал, как её считать на примере бинарного поиска и других алгоритмов.
Кадр: фильм «Мальчишник в Вегасе»
Редакция «Код» Skillbox Media
Онлайн-журнал для тех, кто влюблён в код и информационные технологии. Пишем для айтишников и об айтишниках.
об эксперте
Software Engineer, разрабатывает системы управления городской инфраструктурой для мегаполисов. Основная деятельность: backend, database engineering. Ведёт твиттер @ValeriiZhyla и пишет научные работы по DevOps.
Ссылки
Сегодня я расскажу о сложности алгоритмов, или, как её часто называют, Big O Notation. Статья рассчитана на новичков, поэтому постараюсь изложить идеи и концепции просто, не теряя важных деталей.
Время и память — основные характеристики алгоритмов
Алгоритмы описывают с помощью двух характеристик — времени и памяти.
Время — это… время, которое нужно алгоритму для обработки данных. Например, для маленького массива — 10 секунд, а для массива побольше — 100 секунд. Интуитивно понятно, что время выполнения алгоритма зависит от размера массива.
Но есть проблема: секунды, минуты и часы — это не очень показательные единицы измерения. Кроме того, время работы алгоритма зависит от железа, на котором он выполняется, и других внешних факторов. Поэтому время считают не в секундах и часах, а в количестве операций, которые алгоритм совершит. Это надёжная и, главное, независимая от железа метрика.
Когда говорят о Time Complexity или просто Time, то речь идёт именно о количестве операций. Для простоты расчётов разница в скорости между операциями обычно опускается. Поэтому, несмотря на то, что деление чисел с плавающей точкой требует от процессора больше действий, чем сложение целых чисел, обе операции в теории алгоритмов считаются равными по сложности.
Запомните: в О-нотации на операции с одной или двумя переменными вроде i++, a * b, a / 1024, max(a,b) уходит всего одна единица времени.
Память, или место, — это объём оперативной памяти, который потребуется алгоритму для работы. Одна переменная — это одна ячейка памяти, а массив с тысячей ячеек — тысяча ячеек памяти.
В теории алгоритмов все ячейки считаются равноценными. Например, int a на 4 байта и double b на 8 байт имеют один вес. Потребление памяти обычно называется Space Complexity или просто Space, редко — Memory.
Алгоритмы, которые используют исходный массив как рабочее пространство, называют in-place. Они потребляют мало памяти и создают одиночные переменные — без копий исходного массива и промежуточных структур данных. Алгоритмы, требующие дополнительной памяти, называют out-of-place. Прежде чем использовать алгоритм, надо понять, хватит ли на него памяти, и если нет — поискать менее прожорливые альтернативы.
Статья написана на основе треда Валерия в его аккаунте в Twitter. Автор благодарит @usehex за помощь в создании материала.
Что такое O(n)
Давайте вспомним 8-й класс и разберёмся: что значит запись O(n) с математической точки зрения. При расчёте Big O Notation используют два правила:
Константы откидываются. Нас интересует только часть формулы, которая зависит от размера входных данных. Проще говоря, это само число n, его степени, логарифмы, факториалы и экспоненты, где число находится в степени n.
Примеры:
O(2n * log n) = O(n * log n)
Если в O есть сумма, нас интересует самое быстрорастущее слагаемое. Это называется асимптотической оценкой сложности.
Примеры:
O(n^3 + 100n * log n) = O(n^3)
Хороший, плохой, средний
У каждого алгоритма есть худший, средний и лучший сценарии работы — в зависимости от того, насколько удачно выбраны входные данные. Часто их называют случаями.
Худший случай (worst case) — это когда входные данные требуют максимальных затрат времени и памяти.
Например, если мы хотим отсортировать массив по возрастанию (Ascending Order, коротко ASC), то для простых алгоритмов сортировки худшим случаем будет массив, отсортированный по убыванию (Descending Order, коротко DESC).
Для алгоритма поиска элемента в неотсортированном массиве worst case — это когда искомый элемент находится в конце массива или если элемента нет вообще.
Лучший случай (best case) — полная противоположность worst case, самые удачные входные данные. Правильно отсортированный массив, с которым алгоритму сортировки вообще ничего делать не нужно. В случае поиска — когда алгоритм находит нужный элемент с первого раза.
Средний случай (average case) — самый хитрый из тройки. Интуитивно понятно, что он сидит между best case и worst case, но далеко не всегда понятно, где именно. Часто он совпадает с worst case и всегда хуже best case, если best case не совпадает с worst case. Да, иногда они совпадают.
Как определяют средний случай? Считают статистически усреднённый результат: берут алгоритм, прокручивают его с разными данными, составляют сводку результатов и смотрят, вокруг какой функции распределились результаты. В общем, расчёт average case — дело сложное. А мы приступаем к конкретным алгоритмам.
Линейный поиск
Начнём с самого простого алгоритма — линейного поиска, он же linear search. Дальнейшее объяснение подразумевает, что вы знаете, что такое числа и как устроены массивы. Напомню, это всего лишь набор проиндексированных ячеек.
Допустим, у нас есть массив целых чисел arr, содержащий n элементов. Вообще, количество элементов, размер строк, массивов, списков и графов в алгоритмах всегда обозначают буквой n или N. Ещё дано целое число x. Для удобства обусловимся, что arr точно содержит x.
Задача: найти, на каком месте в массиве arr находится элемент 3, и вернуть его индекс.
Меткий человеческий глаз сразу видит, что искомый элемент содержится в ячейке с индексом 2, то есть в arr[2]. А менее зоркий компьютер будет перебирать ячейки друг за другом: arr[0], arr[1]… и так далее, пока не встретит тройку или конец массива, если тройки в нём нет.
Теперь разберём случаи:
Worst case. Больше всего шагов потребуется, если искомое число стоит в конце массива. В этом случае придётся перебрать все n ячеек, прочитать их содержимое и сравнить с искомым числом. Получается, worst case равен O(n). В нашем массиве худшему случаю соответствует x = 2.
Best case. Если бы искомое число стояло в самом начале массива, то мы бы получили ответ уже в первой ячейке. Best case линейного поиска — O(1). Именно так обозначается константное время в Big O Notation. В нашем массиве best case наблюдается при x = 7.
Average case. В среднем случае результаты будут равномерно распределены по массиву. Средний элемент можно рассчитать по формуле (n + 1) / 2, но так как мы отбрасываем константы, то получаем просто n. Значит, average case равен O(n). Хотя иногда в среднем случае константы оставляют, потому что запись O(n / 2) даёт чуть больше информации.
Псевдокод
Хорошо, мы уже три минуты обсуждаем linear search, но до сих пор не видели кода. Потерпите, скоро всё будет. Но сперва познакомимся с очень полезным инструментом — псевдокодом.
Разработчики пишут на разных языках программирования. Одни похожи друг на друга, а другие — сильно различаются. Часто мы точно знаем, какую операцию хотим выполнить, но не уверены в том, как она выглядит в конкретном языке.
Возьмём хотя бы получение длины массива. По историческим причинам практически во всех языках эта операция называется по-разному: .length, length(), len(), size(), .size — попробуй угадай! Как же объяснить свой код коллегам, которые пишут на другом языке? Написать программу на псевдокоде.
Псевдокод — достаточно формальный, но не слишком требовательный к мелочам инструмент для изложения мыслей, не связанный с конкретным языком программирования.
Прелесть псевдокода в том, что конкретных правил для его написания нет. Я, например, предпочитаю использовать смесь синтаксиса Python и C: обозначаю вложенность с помощью отступов и называю методы в стиле Python.
А вот и пример псевдокода для нашей задачи, со всеми допущениями и упрощениями. Метод должен возвращать -1, если arr пуст или не содержит x:
Бинарный поиск
Следующая остановка — binary search, он же бинарный, или двоичный, поиск.
В чём отличие бинарного поиска от уже знакомого линейного? Чтобы его применить, массив arr должен быть отсортирован. В нашем случае — по возрастанию.
Часто binary search объясняют на примере с телефонным справочником. Возможно, многие читатели никогда не видели такую приблуду — это большая книга со списками телефонных номеров, отсортированных по фамилиям и именам жителей. Для простоты забудем об именах.
Итак, есть огромный справочник на тысячу страниц с десятками тысяч пар «фамилия — номер», отсортированных по фамилиям. Допустим, мы хотим найти номер человека по фамилии Жила. Как бы мы действовали в случае с линейным поиском? Открыли бы книгу и начали её перебирать, строчку за строчкой, страницу за страницей: Астафьев… Безье… Варнава… Ги… До товарища Жилы он дошёл бы за пару часов, а вот господин Янтарный заставил бы алгоритм попотеть ещё дольше.
Бинарный поиск мудрее и хитрее. Он открывает книгу ровно посередине и смотрит на фамилию, например Мельник — буква «М». Книга отсортирована по фамилиям, и алгоритм знает, что буква «Ж» идёт перед «М».
Алгоритм «разрывает» книгу пополам и выкидывает часть с буквами, которые идут после «М»: «Н», «О», «П»… «Я». Затем открывает оставшуюся половинку посередине — на этот раз на фамилии Ежов. Уже близко, но Ежов не Жила, а ещё буква «Ж» идёт после буквы «Е». Разрываем книгу пополам, а левую половину с буквами от «А» до «Е» выбрасываем. Алгоритм продолжает рвать книгу пополам до тех пор, пока не останется единственная измятая страничка с заветной фамилией и номером.
Перенесём этот принцип на массивы. У нас есть отсортированный массив arr и число 7, которое нужно найти. Почему поиск называется бинарным? Дело в том, что алгоритм на каждом шаге уменьшает проблему в два раза. Он буквально отрезает на каждом шаге половину arr, в которой гарантированно нет искомого числа.
На каждом шаге мы проверяем только середину. При этом есть три варианта развития событий:
- попадаем в 7 — тогда проблема решена;
- нашли число меньше 7 — отрезаем левую половину и ищем в правой половине;
- нашли число больше 7 — отрезаем правую половину и ищем в левой половине.
Почему это работает? Вспомните про требование к отсортированности массива, и всё встанет на свои места.
Итак, смотрим в середину. Карандаш будет служить нам указателем.
В середине находится число 5, оно меньше 7. Значит, отрезаем левую половину и проверенное число. Смотрим в середину оставшегося массива:
В середине число 8, оно больше 7. Значит, отрезаем правую половинку и проверенное число. Остаётся число 7 — как раз его мы и искали. Поздравляю!
Теперь давайте попробуем записать это в виде красивого псевдокода. Как обычно, назовём середину mid и будем перемещать «окно наблюдения», ограниченное двумя индексами — low (левая граница) и high (правая граница).
Несколько слов об этой весёлой компании:
- Big O обозначает верхнюю границу сложности алгоритма. Это идеальный инструмент для поиска worst case.
- Big Omega (которая пишется как подкова) обозначает нижнюю границу сложности, и её правильнее использовать для поиска best case.
- Big Theta (пишется как О с чёрточкой) располагается между О и омегой и показывает точную функцию сложности алгоритма. С её помощью правильнее искать average case.
- Small o и Small omega находятся по краям этой иерархии и используются в основном для сравнения алгоритмов между собой.
«Правильнее» в данном контексте означает — с точки зрения математических пейперов по алгоритмам. А в статьях и рабочей документации, как правило, во всех случаях используют «Большое „О“».
Если хотите подробнее узнать об остальных нотациях, посмотрите интересный видос на эту тему. Также полезно понимать, как сильно отличаются скорости возрастания различных функций. Вот хороший cheat sheet по сложности алгоритмов и наглядная картинка с графиками оттуда:
Хоть картинка и наглядная, она плохо передаёт всю бездну, лежащую между функциями. Поэтому я склепал таблицу со значениями времени для разных функций и N. За время одной операции взял 1 наносекунду:
Скрытые константы
В последнем разделе поговорим о скрытых константах. Это хитрая штука, там собака зарыта.
Возьмём умножение матриц. При размерности матрицы n * n наивный алгоритм, который многие знают с начальных курсов универа, «строчка на столбик» имеет кубическую временную сложность O(n^3). Кубическая, зато честная. Без констант и O(10000 * n^3) под капотом. И памяти не ест — только время.
У Валерия есть отдельный тред об умножении матриц.
В некоторых алгоритмах умножения матриц степень n сильно «порезана». Самые «быстрые» из них выдают время около O(n^2,37). Какой персик, правда? Почему бы нам не забыть про «наивный» алгоритм?
Проблема в том, что у таких алгоритмов огромные константы. В пейперах гонятся за более компактной экспонентой, а степени отбрасываются. Я не нашёл внятных значений констант. Даже авторы оригинальных пейперов называют их просто «очень большими».
Давайте от балды возьмём не очень большую константу 100 и сравним n^3 c 100 * n^2,37. Правая функция даёт выигрыш по сравнению с левой для n, начинающихся с 1495. А ведь мы взяли довольно скромную константу. Подозреваю, что на практике они не в пример больше…
В то же время умножение матриц 1495 × 1495 — очень редкий случай. А матрицы миллиард на миллиард точно нигде не встретишь. Да простит меня Император Душнил с «Хабра» за вольное допущение 🙂
Такие алгоритмы называются галактическими, потому что дают выигрыш только на масштабах, нерелевантных для нас. А в программном умножении матриц, если я правильно помню курс алгоритмов и умею читать «Википедию», очень любят алгоритм Штрассена с его O(2,807) и маленькими константами. Но и те, к сожалению, жрут слишком много памяти.
Читайте также:
- Как работают хорошие разработчики: 5 важных принципов
- Как устроена разработка в большом финтехе: при чём тут Scala и за что не любят Java
- «Один разработчик заменяет пять программистов на JavaScript»: для чего нужен Haskell
О МЕТОДАХ ОЦЕНКИ СЛОЖНОСТИ АЛГОРИТМОВ Текст научной статьи по специальности «Математика»
В статье рассматриваются некоторые методы оценки сложности алгоритмов решения ряда задач. Крайне медленная работа некоторых алгоритмов доказывает актуальность выяснения практической значимости алгоритмов. Обозначение «Biq О» принято как наиболее актуальный способ оценки сложности алгоритма . Полиномиальные алгоритмы считаются более подходящими для практического использования.
i Надоели баннеры? Вы всегда можете отключить рекламу.
Похожие темы научных работ по математике , автор научной работы — Керимов В.А., Гаджиев Ф.Г.
Цифровая обработка сигналов на основе интерполяции по Ньютону элементов базиса
О сложности решения уравнений малой степени в кольце целых чисел и кольцах вычетов
Численные эксперименты по оценке временной сложности некоторых алгоритмов
Параллельная сортировка на основе бинарного дерева и слияния по матрицам сравнений
Параллельное построение двоичного дерева на основе сортировки
i Не можете найти то, что вам нужно? Попробуйте сервис подбора литературы.
i Надоели баннеры? Вы всегда можете отключить рекламу.
METHODS FOR EVALUATING COMPLEXITY OF ALGORITHMS
The article discusses some methods for estimating the complexity of algorithms for solving a number of problems. The extremely slow operation of some algorithms proves the relevance of finding out the practical significance of algorithms. The designation «Biq O» is accepted as the most relevant way to evaluate the complexity of the algorithm. Polynomial algorithms are considered more suitable for practical use.
Текст научной работы на тему «О МЕТОДАХ ОЦЕНКИ СЛОЖНОСТИ АЛГОРИТМОВ»
канд. тех. наук, доцент кафедры «Общая и прикладная математика» Азербайджанский государственный университет нефти и промышленности
(г. Баку, Азербайджан)
канд. тех. наук, доцент кафедры «Общая и прикладная математика» Азербайджанский государственный университет нефти и промышленности
(г. Баку, Азербайджан)
О МЕТОДАХ ОЦЕНКИ СЛОЖНОСТИ АЛГОРИТМОВ
Аннотация: в статье рассматриваются некоторые методы оценки сложности алгоритмов решения ряда задач. Крайне медленная работа некоторых алгоритмов доказывает актуальность выяснения практической значимости алгоритмов. Обозначение «Biq О» принято как наиболее актуальный способ оценки сложности алгоритма. Полиномиальные алгоритмы считаются более подходящими для практического использования.
Ключевые слова: сложность алгоритмов, Biq O нотация, Little o нотация, задача о загрузке, схема Горнера, задача o коммивояжере, методы сортировки информации.
В процессе решения различных вычислительных задач не трудно заметить, как медленно работают многие алгоритмы. Одной из основных причин замедления вычисления является колоссальное число сравнений, связанных с перебором вариантов. Поэтому очень актуален вопрос аналитической оценки практичности применяемого алгоритма. Ниже рассматриваются аналитические методы оценки сложности некоторых алгоритмов [1].
Оценка сложности умножения матриц. При умножении матриц A[1:m,1:k], B[1:k,1:p] строится матрица C[1:m,1:p], для построения каждой
Оценка сложности вычисления значения полинома Р(х) = а0 хп + ajx»-1 + a2xn-2 + —+ an в заданной точке общим методом. Для вычисления значения каждого одночлена aiXn-i требуется n-i операций. Для суммирования полученных одночленов потребуется n операций сложения. Таким образом, число всех операций оценивается по формуле: n+(n-1)+(n-
2)+. +2+1 +n=n(n2+1) I n=0,5n2+ 1,5n=O(n2).
Оценка сложности вычисления значения полинома в заданной точке по схеме Горнера [3]. Покажем, что при применении схемы Горнера число вычислений значительно сокращается. Например, рассмотрим многочлен 3-го порядка: P(x) = 9×3 + 5×2 + 8x + 7 = (9×2 + 5x + 8)x + 7 = ((9x + 5)x + 8)x + 7. Нетрудно заметить, что для вычисления последнего выражения необходимо выполнить по три операции умножения и сложения. Если степень многочлена равна n, то применяя схему Горнера необходимо выполнить 2n вычислений, при этом сложность вычислений будет выражаться формулой O(n). Следовательно, метод Горнера лучше, чем общий метод.
Оценка сложности методов сортировки. Оценка практической сложности алгоритма представляется более трудной задачей в сравнении с теоретической сложностью [2,4]. Время работы алгоритма не только зависит от объема входной информации, но также от расположения входных данных, от их значений и т.д., например, скорость работы некоторых алгоритмов сортировки
может значительно сократиться, если входной поток информации частично отсортирован. На практике рассматриваются следующие категории сложности алгоритмов сортировки:
1) Максимальная сложность — это оценка времени работы алгоритма в наиболее неблагоприятных условиях;
2) Минимальная сложность — это оценка времени работы алгоритма в наиболее благоприятных условиях;
3) Оценка сложности алгоритма в среднем, — это полусумма максимальной и минимальной сложностей.
Определение: Сложностью некоторого алгоритма А, выполняющего упорядочивание последовательности из п элементов называется количество всех сравнений в наихудшем случае расположения элементов.
В качестве функций временной сложности сортировки, как правило, рассматриваются следующие функции О(п2),О(п^п),О(п).
Оценка сложности сортировки выбором осуществляется при помощи сравнения каждого элемента со всеми остальными элементами, число сравнений
при определении х1 равно п -1; при определении х2 , п — 2 и т.д. в результате
сортировки по возрастанию получаем последовательность: X1,х2. хп при
Для обозначения всех сравнений введем функцию Т (п) =
(п- 1)+(п-2)+. +2 +1 = п(п^ 1). Тогда для больших значений параметра п
функция Т (п) приблизительно будет равно: Т (п)« —.
Оценка сложности метода деления «пополам». В каждой последовательности можно найти упорядоченный фрагмент. Суть настоящего метода, взять каждый элемент из неупорядоченной части и привнести его в упорядоченную среду методом деления «пополам». Если в упорядоченной последовательности число элементов четное, метод деления пополам
выполняется без проблемы, если же — нечетное при разбиении отрезка «пополам» в одной области будет на единицу больше элементов. Пусть,
х15х2. хр,хр+1. хк расставлены по возрастанию. Рассмотрим два случая: 1) к — четн°е число, тогда : р — к; 2) к — нечетное чюю, товд для оценки р _ использовать альтернативные формулы:
р — , или р — к^ . Допустим, и (к) — функция, которая оценивает
количество сравнений при включении нового элемента в упорядоченную последовательность с к элементами. Выполним анализ функции с возрастанием аргумента к. При к=1, очевидно, и(1)-1. При к=2 количество максимальных сравнений равно 2. Вообще, анализ дает следующие результаты: и(2)=2, и(3)=1 + и(1)=2, и(4)=1 + и(2)=3.
В формуле (1) запись показывает целую часть деления числа к на 2.
и(35)=1 + и(17)=2+и(8)=3+и(4)=4+и(2)=5+и(1)=6. Введем новую функцию Т2(п) для оценки сложности рассматриваемого метода.
Выполним оценку Т2(п) при наихудшем случае расположения элементов заданного массива, т.е. предполагаем, в массиве нет упорядоченного фрагмента. В этом случае возьмем любой элемент заданной последовательности, применяя метод деления «пополам» шаг за шагом постепенно расширяем упорядоченную область. Тогда для оценки количества сравнений в наихудшем случае можно использовать следующую формулу:
Например, при п=5 по формуле (2) получаем: Т(5)< и(1) +. + и(4) = 1 + 2 + 2 + 3 = 8.
С другой стороны при п = 5 количество сравнений при обменной
сортировке будет равно: Т (5) = 20 = 10. Сравнение результатов Т (5) и Т2(5)
показывает, что метод деления пополам является эффективным. Более того, с возрастанием числа п преимущество этого метода становится подавляющим.
Например, при п=10 получаем: Т(10) = 90 = 45; Т2(10) < 25; а при п= 20 получаем:
Т (20) = 190, Т2 (20) < 69.
Задача о загрузке — это задача о рациональной загрузке судна, которое имеет ограничения по объему или грузоподъемности. Каждый помещенный на судно груз приносит определенную прибыль. Задача состоит в определении загрузки судна такими грузами, которые приносят наибольшую суммарную прибыль. Допустим, всего 3 вида грузов, грузоподъемность судна 10000 кг. Судно надо загрузить так, чтобы общий вес грузов был максимально близок к 10000 кг, но не завышал этот предел. Пусть веса грузов: холодильник (Х) — 100 кг, генератор (Г) -75 кг, кондиционер (К) — 50 кг. Ниже в скобках указаны количества грузов по выбранным наименованиям. При бинарном ветвлении дерева перебора получим следующие альтернативные планы загрузки: 1. Х(20),Г(50), К(85), 2. Х(20),Г(100), К(10), 3. Х(30),Г(70), К(35), 4. Х(30),Г(90), К(5). Таким образом, при каждом бинарном ветвлении количества холодильников и генераторов было построено 22=4 вариантов. Если грузов п наименований, при бинарном ветвлении количество вариантов будет 2П-1. Например, при п=101, число вариантов будет 210°~103° . Пусть коммпьютер за секунду выполняет 109 операций. Подсчитаем время, необходимое для сравнения вариантов и, следовательно, выбора оптимального из них: (103° /109) сек. = 1021 сек. ~ 107 • 3170978 год. Следовательно, при таком подходе задача практически неразрешима. Да, скорость света высочайшая, но в сравнении с размерами вселенной она мизерная!
1. Cormen, Thomas И.; Leiserson, Charles E.; Rivest, Ronald L. & Stein, Clifford Introduction to Algorithms. Chapter 1: Foundations (Second ed.). Cambridge, MA: MIT Press and McGraw-Hill. pp. 3-122. ISBN 0-262-03293-7, 2001.
2. Donald Knuth, The Art of Computer Programming, Volume 3: Sorting and Searching, Second Edition. ISBN 0-201-89685-0, Section 5.4: External Sorting, pp. 248-379. Addison-Wesley, 1998.
3. Андерсон Дж.А. Дискретная математика и комбинаторика. : Пер. С англ.-М.: Издательский дом «Вильямс», 2004, 960 с.
4. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи.- М.: Мир, 1982, 191 с.
Azerbaijan State University of Petroleum and Industry (Baku, Azerbaijan)
Azerbaijan State University of Petroleum and Industry (Baku, Azerbaijan)
METHODS FOR EVALUATING COMPLEXITY OF ALGORITHMS
Abstract: the article discusses some methods for estimating the complexity of algorithms for solving a number ofproblems. The extremely slow operation of some algorithms proves the relevance of finding out the practical significance of algorithms. The designation «Biq O» is accepted as the most relevant way to evaluate the complexity of the algorithm. Polynomial algorithms are considered more suitable for practical use.
Keywords: complexity of algorithms, Biq O notation, Little o notation, loading problem, Gorner scheme, traveling salesman problem, information sorting methods.
Оценка сложности алгоритмов, или Что такое О(log n)
Если вы всё ещё не понимаете, что такое вычислительная сложность алгоритмов, и ждете простое и понятное объяснение, — эта статья для вас.
Наверняка вы не раз сталкивались с обозначениями вроде O(log n) или слышали фразы типа «логарифмическая вычислительная сложность» в адрес каких-либо алгоритмов. И если вы хотите стать хорошим программистом, но так и не понимаете, что это значит, — данная статья для вас.
Оценка сложности
Сложность алгоритмов обычно оценивают по времени выполнения или по используемой памяти. В обоих случаях сложность зависит от размеров входных данных: массив из 100 элементов будет обработан быстрее, чем аналогичный из 1000. При этом точное время мало кого интересует: оно зависит от процессора, типа данных, языка программирования и множества других параметров. Важна лишь асимптотическая сложность, т. е. сложность при стремлении размера входных данных к бесконечности.
Допустим, некоторому алгоритму нужно выполнить 4n3 + 7n условных операций, чтобы обработать n элементов входных данных. При увеличении n на итоговое время работы будет значительно больше влиять возведение n в куб, чем умножение его на 4 или же прибавление 7n . Тогда говорят, что временная сложность этого алгоритма равна О(n3) , т. е. зависит от размера входных данных кубически.
Использование заглавной буквы О (или так называемая О-нотация) пришло из математики, где её применяют для сравнения асимптотического поведения функций. Формально O(f(n)) означает, что время работы алгоритма (или объём занимаемой памяти) растёт в зависимости от объёма входных данных не быстрее, чем некоторая константа, умноженная на f(n) .
Примеры
O(n) — линейная сложность
Такой сложностью обладает, например, алгоритм поиска наибольшего элемента в не отсортированном массиве. Нам придётся пройтись по всем n элементам массива, чтобы понять, какой из них максимальный.
O(log n) — логарифмическая сложность
Простейший пример — бинарный поиск. Если массив отсортирован, мы можем проверить, есть ли в нём какое-то конкретное значение, методом деления пополам. Проверим средний элемент, если он больше искомого, то отбросим вторую половину массива — там его точно нет. Если же меньше, то наоборот — отбросим начальную половину. И так будем продолжать делить пополам, в итоге проверим log n элементов.
O(n2) — квадратичная сложность
Такую сложность имеет, например, алгоритм сортировки вставками. В канонической реализации он представляет из себя два вложенных цикла: один, чтобы проходить по всему массиву, а второй, чтобы находить место очередному элементу в уже отсортированной части. Таким образом, количество операций будет зависеть от размера массива как n * n , т. е. n2 .
Бывают и другие оценки по сложности, но все они основаны на том же принципе.
Также случается, что время работы алгоритма вообще не зависит от размера входных данных. Тогда сложность обозначают как O(1) . Например, для определения значения третьего элемента массива не нужно ни запоминать элементы, ни проходить по ним сколько-то раз. Всегда нужно просто дождаться в потоке входных данных третий элемент и это будет результатом, на вычисление которого для любого количества данных нужно одно и то же время.
Аналогично проводят оценку и по памяти, когда это важно. Однако алгоритмы могут использовать значительно больше памяти при увеличении размера входных данных, чем другие, но зато работать быстрее. И наоборот. Это помогает выбирать оптимальные пути решения задач исходя из текущих условий и требований.
Наглядно
Время выполнения алгоритма с определённой сложностью в зависимости от размера входных данных при скорости 106 операций в секунду:
Тут можно посмотреть сложность основных алгоритмов сортировки и работы с данными.
Если хочется подробнее и сложнее, заглядывайте в нашу статью из серии «Алгоритмы и структуры данных для начинающих».
Следите за новыми постами по любимым темам
Подпишитесь на интересующие вас теги, чтобы следить за новыми постами и быть в курсе событий.