Лекция
Привет, сегодня поговорим про эффективность алгоритма, обещаю рассказать все что знаю. Для того чтобы лучше понимать что такое эффективность алгоритма , настоятельно рекомендую прочитать все из категории Алгоритмы и теория алгоритмов.
" Поразительно, скольким программистам приходится слишком дорогим способом выяснять, что их программа не может обработать входные данные раньше, чем через несколько дней машинного времени. Лучше было бы предугадать такие случаи с помощью карандаша и бумаги. "
С. Гудман (S. Goodman), С. Хидетниеми (S. Hedetniemi)
" Лучше меньше, да лучше. "
В.И. Ульянов (Ленин)
эффективность алгоритма — это свойство алгоритма, которое связано с вычислительными ресурсами, используемыми алгоритмом. Алгоритм должен быть проанализирован с целью определения необходимых алгоритму ресурсов. Эффективность алгоритма можно рассматривать как аналог производственной производительности повторяющихся или непрерывных процессов.
Для достижения максимальной эффективности мы желаем уменьшить использование ресурсов. Однако различные ресурсы (такие как время и память) нельзя сравнить напрямую, так что какой из двух алгоритмов считать более эффективным часто зависит от того, какой фактор более важен, например, требование высокой скорости, минимального использования памяти или другой меры эффективности
Алгоритм считается эффективным, если потребляемый им ресурс (или стоимость ресурса) на уровне или ниже некоторого приемлемого уровня. Грубо говоря, «приемлемый» здесь означает «алгоритм будет работать умеренное время на доступном компьютере». Поскольку с 1950-х годов наблюдалось значительное увеличение вычислительной мощности и доступной памяти компьютеров, существующий «приемлемый уровень» не был приемлемым даже 10 лет назад.
Выше мы уже говорили о необходимости анализировать конструируемый алгоритм. Такой анализ должен дать четкое представление, во-первых, о емкостной и, во-вторых, о временнОй сложности процесса.
Первая часть вполне ясна: речь идет о размерах памяти, в которой предстоит размещать все данные, участвующие в вычислительном процессе. Естественно, к ним относятся входные наборы, промежуточная и выходная информация. Возможно, не все перечисленные наборы требуют одновременного хранения, - что ж, значит, удается сэкономить. В ряде случаев, впрочем, оценка емкостной сложности становится менее очевидной: так обстоит дело при использовании динамических структур, но об этом - в другой главе.
А вот анализу временнОй трудоемкости мы уделим внимание уже сейчас.
Для оценки эффективности алгоритма( не следует путать с сложностью), обычно используются несколько подходов:
Время выполнения: измеряется время, необходимое для выполнения алгоритма. Этот параметр часто оценивается в больших вычислительных задачах, где требуется обработка больших объемов данных. Время выполнения может быть измерено на реальных данных или на синтетических данных.
Память: измеряется объем памяти, необходимой для выполнения алгоритма. Этот параметр также важен при работе с большими объемами данных, когда память может стать узким местом.
Точность: измеряется насколько хорошо алгоритм решает поставленную задачу. Это может быть оценено по сравнению с другими алгоритмами или по сравнению с известным оптимальным решением.
Масштабируемость: оценка того, насколько алгоритм может быть масштабирован при увеличении размера данных или увеличении количества вычислительных ресурсов.
Устойчивость: оценка того, как алгоритм справляется с шумом или неожиданными изменениями данных.
Сложность: анализируется количество операций, необходимых для выполнения алгоритма. Чем меньше количество операций, тем более эффективен алгоритм.
Кроме того, при оценке эффективности алгоритма важно учитывать его применимость к конкретной задаче и требования пользователя. Например, для некоторых задач более важным параметром может быть точность, в то время как для других - скорость выполнения.
Итак, поставлена некоторая задача, и для ее решения спроектирован алгоритм. Он описывает вычислительный процесс, который завершается за конечное число действий-шагов. Мы уже говорили, что реальное время выполнения каждого отдельного шага зависит от конкретного вычислительного устройства. Иначе говоря, неотъемлемым участником вычислительного процесса, - не алгоритма! - является исполнитель. А вот имея ввиду предполагаемого исполнителя, не грех заранее оценить его вычислительные способности.
Можно сказать, что алгоритм должен быть понятен исполнителю. Это означает, что любое предписание алгоритма должно входить в тот фиксированный набор инструкций, которые исполнитель умеет реализовывать. Скажем, ваш карманный калькулятор рассчитан на выполнение нескольких арифметических операций, а более мощный, программируемый калькулятор, уже готов выполнять несложные программы. Соответственно, наборы встроенных, элементарных, инструкций у этих устройств различаются. Притом, любая команда, которую готов выполнить второй калькулятор, все равно состоит из некоторого числа арифметических и логических операций. Другое дело, что нам не приходится их вызывать по отдельности. Таким образом, либо алгоритм явно предписывает выполнять арифметико-логические операции, - и такой уровень программирования рассчитан непосредственно на работу процессора, - либо используются "укрупненные" инструкции, и для их обработки применяется специальный язык.
Так, общение клиента с банкоматом предусматривает участие двух исполнителей алгоритма - человека и банкомата, причем первый из них обращается ко второму посредством кнопочного интерфейса. Опытный владелец пластиковой карты знаком с процедурой, тем не менее, второй участник процесса не учитывает компетентность клиента, и потому на табло высвечиваются поочередно все необходимые инструкции. Как видим, разработчики системы, обеспечивающей этот диалог, довели пошаговую детализацию алгоритма до определенного уровня "компетентности", разбив укрупненные шаги - "снятия наличности" или "получения справки о счете" - на шаги более мелкие.
Как мы выяснили, исполнитель нашего алгоритма должен "уметь" выполнить любую инструкцию из числа тех, которые он воспринимает как элементарные, а никакие другие он и не выполнит. Собственно, одно из различий между процессорами компьютеров состоит в несовпадении их "личных" наборов инструкций.
Но было бы нелепо в предлагаемом читателю курсе ориентироваться на столь "интеллектуально ограниченного" исполнителя, каким является обыкновенный процессор. Напротив, "способности" нашего подразумеваемого исполнителя должны постепенно развиваться. Потому, по мере удаления от начальных страниц, степень детализации будет уменьшаться, и алгоритмы будут описываться в укрупненных шагах. Так, опытный повар вполне готов исполнить предписание "приготовить ростбиф", - помните, мы с ним выше сталкивались? - как элементарную инструкцию.
Предположим, алгоритм для решения некоторой задачи нам удалось построить. Раз так, что мешает предположить существование и другого алгоритма, и еще следующего? Но если удается сконструировать целый ряд различных алгоритмов решения одной и той же задачи, то кажется разумным - выбрать "наилучший". Об этом говорит сайт https://intellect.icu . Что под этим следует понимать?
Как правило, речь идет о таком варианте решения, который, в сравнении с конкурентами, нуждается в наименее продолжительном по времени вычислительном процессе. Разумеется, давать такую оценку правомерно, лишь имея ввиду одного и того же потенциального исполнителя.
Далее: скорость реализации выбираемого алгоритма может существенно зависеть от содержания набора входных данных. Скажем, быстрый "в среднем" механизм способен давать сбои в отдельных "плохих" случаях. И, если задача должна наверняка решаться за определенное время работы процессора, то в этом случае, вероятно, мы предпочтем алгоритм более медленный в среднем, зато надежный в худших ситуациях.
За примерами вновь обратимся к некомпьютерной сфере. Чтобы выпить чашку кофе, надо, во всяком случае, подогреть воду. Достаточно удобна и эффективна в этом случае кофеварка или мощный электрочайник. Если к вам в дом, - а это весьма вероятно, - подведено электричество, то способ решения задачи, привлекающий один из указанных приборов, стоит предпочесть в большинстве случаев. Однако неполадки в распределительном электрощите, сколь бы редко они ни возникали, лишат вас ожидаемого удовольствия (как и автора, который ссылается здесь на собственный печальный опыт, когда одновременно с кофеваркой перестает работать и компьютер). Так что газовые плиты пока не стоит отменять.
Впрочем, остается и самый надежный, хотя и наиболее трудоемкий метод: вскипятить воду на открытом огне, разложив небольшой костер. Чтобы читатель не забывал анализировать и емкостную сложность алгоритма, заметим, что последний пример сочетает свойства наихудшей эффективности как по времени, так и по требованиям к ресурсам, учитывая безвозвратный расход горючего и низкий коэффициент полезного действия при изменении агрегатного состояния. Однако даже такой алгоритм имеет право на существование!
Итак, давая оценку быстродействия алгоритма, следует рассмотреть поведение вычислительного процесса в среднем и, отдельно, в экстремальных для него условиях, то есть - в худшем случае.
Моделирование "худших" случаев всегда связано с содержанием самого алгоритма. Можно предложить лишь малое число рецептов выделения и рассмотрения подобных ситуаций. Один из них состоит в проверке поведения алгоритма на входных данных, принимающих граничные значения из разрешенного диапазона. Другой рецепт: тестировать алгоритм на максимально больших по объему входных наборах, что важно для анализа как временнОй, так и емкостной эффективности.
Пожалуй, умение предвидеть "нехорошие" ситуации, - а они нередко возникают при выполнении готовой программы, - как раз и отличает квалифицированного алгоритмиста от обыкновенного кодировщика. В связи с расширением сферы производства программного обеспечения сформировалась даже самостоятельная специализация - "тестеры программ".
Хорошей тренировкой в развитии навыков проектирования контрпримеров к разрабатываемому алгоритму - и, разумеется, программе - станет для читателя выполнение заданий. Построены они по современным, - "олимпиадным", - канонам. Вам будут далее предлагаться многочисленные примеры, решение которых состоит в написании соответствующих программ. Готовые программы предстоит тестировать автоматизированной системе, причем наборы тестов составлены так, чтобы алгоритм прошел через "огонь и воду". Для этого первые тесты проверяют работоспособность "в общем", с точки зрения получения ожидаемого результата, а вот далее, если это соответствует постановке задачи, - "в частности", когда на вход программы подаются "плохие", в рассмотренном нами смысле, наборы.
Однако продолжим обсуждение того, как оценивать временнУю эффективность собственно алгоритма. Обычно ее не связывают с конкретной вычислительной установкой, а оперируют только "шагами". В самом деле, хорошо бы давать такие оценки, которые будут актуальны и "завтра", когда быстродействие техническое, - аппаратное, - наверняка возрастет.
Естественно, любой шаг алгоритма реализуется некоторым числом машинных операций, или тех самых элементарных инструкций исполнителя, поскольку вы вряд ли станете проектировать алгоритм на языке ассемблера. По существу, анализ требует такой степени детализации алгоритма, чтобы в отношении отдельного шага не требовалась его дальнейшая алгоритмическая проработка. Здесь возможны лишь две ситуации: либо фиксированное время исполнения такого шага определено некоторым набором простых, без циклов, команд языка программирования, либо речь идет об "укрупненном" шаге, в отношении которого соответствующий анализ уже проводился и результаты известны.
Рассмотрим примеры.
Пример 1
Алгоритм обмена двух переменных - a и b - реализуется, в общем случае, за три шага, независимо от того, к какому типу простых переменных он применяется: temp ← a a ← b b ← temp
С точки зрения количества машинных операций, две разных ситуации - обмена содержимым между переменными, занимающими одно машинное слово, или занимающими два машинных слова - неравноценны. Но оценка алгоритмической трудоемкости это не учитывает.
Пример 2
Найти сумму натуральных чисел от 1 до заданного n.
Если воспользоваться известной формулой для суммы арифметической прогрессии, то вычисления также потребуют лишь 3 шага: сложение, умножение и деление. Если же реализовать вычислительный процесс как циклический: цикл с параметром, управляющая переменная "пробежит" значения от 1 до n, - то придется выполнить n шагов алгоритма. Сомнений, какой из алгоритмов более эффективен, кажется, не возникает. Однако вспомните о "худших случаях": при небольших значениях n(скажем, от 2 до 4), "медленный" алгоритм, вероятно, предпочтительнее.
Для алгоритмов, подобных только что рассмотренному, - n шагов для обработки n входных значений, - очевидно, что количество шагов является функцией от числа обрабатываемых элементов. Можно считать, что количество шагов является функцией от количества элементов - f(n).
В математике существует специальный механизм оценки скорости роста интересующей исследователя величины: ее сравнивают с какой-нибудь функцией, чье поведение хорошо исследовано. При этом используется обозначение g(n)=O(f(n)), - читается: O-большое), которое мы будем относить к интересующим нас дискретным функциям f(n) натурального n и ко всем функциям g(n), растущим не быстрее f(n). Формулировка "растущим не быстрее" означает, что существует такая пара положительных значений Mи n0, что |g(n)|≤M|f(n0)| для n≥n0. Еще говорят, что функция g(n) - "порядка f(n) для большИх n".
Нотация Big-O - порядок роста или асимптотическая оценка роста. Big-O = O(n): О - объем данных, n – нотация.
Время сортировки массива зависит от размера сортируемого массива и его упорядоченности. Время работы алгоритма определяется числом шагов, которые он выполняет. Будем считать, что срока псевдокода требует не более чем фиксированного количества элементарных операций, если строка не является формулировкой сложных действий. В последнем случае строка соответствует программной функции, а в основном алгоритме ей соответствует вызов той функции. Вызов функции и ее выполнение отличаются по времени.
Такая O-нотация дает нам верхнюю оценку временнОй трудоемкости алгоритма, его асимптотическую сложность. Обратите внимание, что использование констант M и n0, фигурирующих в определении, фактически связано с "большими" значениями аргумента n и мало что дает при его малых значениях.
Укажем несколько важных свойств O-операций:
f(n)=O(f(n))
c·O(f(n))=O(f(n)), где c - некоторая константа
O(f(n))+O(f(n))=O(f(n))
O(O(f(n)))=O(f(n))
O(f(n))·O(g(n))=O(f(n)·g(n))
Кроме введенной терминологии, полезна и другая, так называемая o-нотация ("о-малое"). Обозначение o(f(n)) относится к функциям, которые растут быстрее f(n).
Вновь обращаясь к примеру с суммой арифметической прогрессии, можем сказать, что асимптотическая эффективность алгоритма непосредственного суммирования n элементов соответствует линейной сложности, поскольку его быстродействие, то есть число шагов, согласно свойству (a), есть O(n).
Вообще говоря, если алгоритм связан с обработкой n входных элементов, и аналитического выражения - формулы - для быстрого вычисления результата в нашем распоряжении нет, то достижение лучшей эффективности, чем O(n), если это вообще возможно, следует рассматривать как большой успех.
А вот более трудоемкие алгоритмы, при том же объеме входного набора, существуют, и ускорить процесс далеко не всегда удается.
Пример 3
Независимый выбор пары соседей для первой парты в классе из n учеников можно осуществить n(n-1) способами.
Если предстоит рассмотреть все варианты для выбора наиболее приемлемого в некотором заданном смысле, то трудоемкость алгоритма, очевидно, оценивается как O(n2), или квадратичная. Согласно свойству (b) O-операций, собственно константа, определяющая трудоемкость каждого отдельного шага оценки "приемлемости", скрыта внутри обозначения, и даже может быть нам неизвестна.
Пример 4
Совсем не трудно представить еще менее эффективный алгоритм. Предлагается для набора из n попарно неравных отрезков подсчитать количество всевозможных "троек", из которых получаются невырожденные треугольники.
Здесь, очевидно, предстоит проверить n(n-1)(n-2) вариантов, что соответствует кубической трудоемкости - O(n3).
В наших примерах речь идет о верхних оценках скорости роста трудоемкости. Обычно, при поверхностном анализе алгоритма, такой оценки вполне достаточно, особенно когда речь идет об алгоритмах с трудоемкостью "разного порядка", как то: O(n2) иO(n3). В общем случае, если эффективность алгоритма определяется вычислительной сложностью обработки многочлена порядкаk, часто удовлетворяются оценкой O(nk), не обращая внимания, согласно свойству (b), на старший коэффициент.
Такой подход, как правило, оправдывает себя для "большИх" n. Действительно, как следует из определения O-асимптотики, - и это демонстрируют приводимые графики, - сколь бы ни был мал коэффициент при старшем k-члене и, напротив, велик - при любом другом m-члене (m, вклад первого из них в поведение всего многочлена рано или поздно становится решающим.
Однако нередко представляет интерес более тщательный анализ. В частности, когда сравнивают эффективность двух равноценных, с точки зрения O-асимптотики, алгоритмов. Тогда возникает необходимость в уточнении первого "приближения".
Так, оценка O(n3) в последнем примере получена нами без раскрытия скобок в произведении. Для ее уточнения достаточно проделать несколько умножений:
n(n-1)(n-2)=n3-3n2+2n=n3+O(n2)
или, еще точнее,
n3-3n2+2n=n3-3n2+O(n).
На практике оказывается недостаточно "O(nk)-шкалы" для сравнения временнОй сложности алгоритмов. Так, более эффективным, чем алгоритм с линейной трудоемкостью, является его конкурент, чье поведение оценивается как O(log2n). Еще быстрее работает алгоритм с постоянной трудоемкостью - O(1), с одним из них мы уже имели дело - это алгоритм обмена. Соответственно, "между" O(n) и O(n2) находится место для O(n·log2n). Знакомство с такими алгоритмами нам предстоит.
Классификация алгоритмов по трудоемкости.
|
О (1) |
Большинство инструкций программы запускается один или несколько раз, независимо от n. Т.е. время выполнения программы постоянно. (помещение в стек) |
|
О (n) |
Время выполнения программы линейно зависит от n. Каждый входной элемент подвергается небольшой обработке. (поиск min/max в массиве, значения в связанном списке) (for…; i<n ;...) |
|
О (n2) |
Время выполнения программы является квадратичным. Такие алгоритмы можно использовать для относительно небольших n. Такое время характерно, когда обрабатываются все пары элементов (в цикле двойного уровня вложенности). (сортировки выбором, вставками) |
|
О (n3) |
Алгоритм обрабатывает тройки элементов (возможно, в цикле тройного уровня вложенности) и имеет кубическое время выполнения. Такой алгоритм практически применим только для малых задач. (умножение матриц) |
|
О (logn) |
Программа работает медленнее с ростом n. Такое время характерно для программ, которые сводят большую задачу к набору меньших подзадач, уменьшая на каждом шаге размер подзадачи на некоторый постоянный коэффициент. Общее решение находится в одной из подзадач. Логарифмическая зависимость. (бинарный поиск) |
|
О (n*logn) |
Время выполнения программы пропорционально n*log n возникает тогда, когда алгоритм решает задачу, разбивая ее на меньшие подзадачи, решая их независимо и затем объединяя решения подзадач (комбинация). Линерифмическая зависимост (сортировки быстрая, слиянием) |
|
О (2n) |
Лишь несколько алгоритмов с экспоненциальным временем имеет практическое применение, хотя такие алгоритмы возникают естественным образом при попытке прямого решения задач. (перебор и сравнение различных решений) Для комбинаторных задач нереализуемы. Сведение к приближенному алгоритму с приближенным значением. |
Обычно время выполнения в результате анализа выглядит как многочлен, где главным членом является один из вышеприведенных. Коэффициент при главном члене зависит от количества инструкций во внутреннем цикле. Поэтому так важно максимально упрощать количество инструкций во внутреннем цикле. При росте N начинает доминировать главный член, поэтому остальными слагаемыми в многочлене можно пренебречь.
К сожалению, в одной статье не просто дать все знания про эффективность алгоритма. Но я - старался. Если ты проявишь интерес к раскрытию подробностей,я обязательно напишу продолжение! Надеюсь, что теперь ты понял что такое эффективность алгоритма и для чего все это нужно, а если не понял, или есть замечания, то не стесняйся, пиши или спрашивай в комментариях, с удовольствием отвечу. Для того чтобы глубже понять настоятельно рекомендую изучить всю информацию из категории Алгоритмы и теория алгоритмов
Комментарии
Оставить комментарий
Алгоритмы и теория алгоритмов
Термины: Алгоритмы и теория алгоритмов