Эффективность алгоритма - это свойство алгоритма , которое связано с вычислительными ресурсами, используемыми алгоритмом. Алгоритм должен быть проанализирован с целью определения необходимых алгоритму ресурсов. Эффективность алгоритма можно рассматривать как аналог производственной производительности повторяющихся или непрерывных процессов.
Для достижения максимальной эффективности мы желаем уменьшить использование ресурсов. Однако, различные ресурсы (такие как время и память) нельзя сравнить напрямую, так что какой из двух алгоритмов считать более эффективным часто зависит от того, какой фактор более важен, например, требование высокой скорости, минимального использования памяти или другой меры эффективности.
Заметим, что данная статья НЕ об оптимизации алгоритма, которая обсуждается в статьях оптимизация программы , оптимизирующий компилятор , оптимизация циклов , оптимизатор объектного кода , и так далее. Термин «оптимизация» сам по себе вводит в заблуждение, поскольку всё, что может быть сделано, попадает под определение «улучшение».Энциклопедичный YouTube
1 / 5
✪ CS50. Асимптотические обозначения
✪ 1. Алгоритмы и структуры данных. Введение | Технострим
✪ Алгоритмическая эффективность
✪ Алгоритм Кнута-Морриса-Пратта
✪ 2. Алгоритмы и структуры данных. Списки, стек, очередь, дек | Технострим
Субтитры
Вы, вероятно, слышали как люди говорят о быстрых или эффективных алгоритмах для выполнения той или иной задачи, но что именно понимают под быстротой и эффективностью в случае алгоритмов? В действительности говорят не об измерениях реального времени в секундах или минутах. Потому что компьютерное оборудование и программное обеспечение весьма разнообразно. Моя программа может работать медленнее вашей из-за того, что я запустил её на более старом компьютере, или из-за того, что я одновременно играю в сетевую игру какую-нибудь, которая съедает у меня всю память. Или же я запустил свою программу через другое программное обеспечение, которое по-своему взаимодействует с оборудованием на низком уровне. Это всё равно что сравнивать тёплое с мягким. Только то, что у моего более медленного компьютера уходит больше времени на поиск ответа, ещё не значит, что ваш алгоритм более эффективный. Раз мы не можем напрямую сравнивать время исполнения программ в секундах или минутах, то как нам сравнить два разных алгоритма без зависимости от оборудования или программного обеспечения? Чтобы унифицировать способ измерения алгоритмической эффективности, математики и специалисты в области информатики нашли решение в измерении асимптотической сложности программы и так называемой записи "О большое" для её описания. Формальное определение звучит так: Функция f(x) имеет порядок g(x), если существует такое значение "x", "x₀" и некоторая константа "C", для которых f(x) меньше или равно этой константе, умноженной на g(x) для любого "x" большего, чем "x₀". Однако, не пугайтесь формального определения. Что же это значит на самом деле в менее теоретических терминах? Ну, попросту говоря, это способ анализа того, насколько быстро растёт асемптотическое время исполнения программы. То есть по мере увеличения размера входных данных в сторону бесконечности. Скажем, мы сортируем массив из 1000 элементов и массив из 10. Как вырастет время исполнения программы? Например, представьте подсчёт числа символов в строке простейшим способом, проходом всей строки буква за буквой и добавлением единицы к счётчику каждый раз. Говорят, что алгоритм выполняется за линейное время от количества символов (n) в строке. Или кратко, выполняется за O(n). Почему так? Ну, при таком подходе время, требующееся для прохода всей строки, пропорционально числу символов в ней. Подсчёт числа символов в 20-символьной строке займёт вдвое больше, чем подсчёт в 10-символьной строке, потому что придётся посмотреть на все символы, а просмотр каждого символа занимает одинаковое время. По мере увеличения числа символов время исполнения будет увеличиваться вместе с длиной исходных данных. Теперь, допустим, вы решаете, что линейное время, O(n), -- это не достаточно быстро. Возможно, вы храните огромные строки и не можете позволить себе дополнительное время на проход по всем символам, подсчитывая их один за другим. И вы решаете попробовать кое-что другое. Что если число символов для строки уже будет храниться в переменной, скажем, "len". Оно сохраняется в программе раньше, ещё до того, как вы сохранили самый первый символ своей строки. Тогда всё, что вам нужно будет сделать для нахождения длины строки -- это прочитать значение этой переменной. Вам не пришлось бы вообще смотреть на саму строку, а чтение значения переменной "len" предпологается операцией, выполняющейся за асимптотически постоянное время, или O(1). Почему так? Вспомним, что значит асимптотическая сложность. Как время исполнения изменяется по мере роста размера входных данных? Допустим, вы получаете количество символов в более длинной строке. В общем-то, совершенно не важно, насколько она длинная. Хоть миллион символов. Всё, что нужно будет сделать при таком подходе, чтобы найти длину строки -- это прочитать значение переменной "len", которую вы уже получили. Размер входных данных, в нашем случае строки, длину которой мы хотим найти, вообще не будет влиять на то, как быстро выполняется программа. Эта часть вашей программы будет одинаково быстро выполняться на строке из одного символа и на строке из тысячи символов. И вот поэтому программа будет считаться исполняющейся за постоянное время относительно размера входных данных. Конечно же, есть и недостатки. Вы тратите дополнительную память вашего компьютера для хранения переменной, а также дополнительное время, чтобы заполнить её значение. Но смысл в этом всё равно есть. Время получения количества символов в строке вообще не зависит от длины строки. Итак, оно исполняется за O(1) или за постоянное время. Само собой это не обязательно значит, что ваш код выполняет только один шаг. Однако, не важно сколько будет шагов, если их число не меняется при изменении размера входных данных. Оно будет асимптотически постоянным, что мы обозначаем как O(1). Как вы, возможно, предположили есть много различных "больших О" для измерения времени исполнения алгоритмов. Алгоритмы O(n²) асимптотически медленнее алгоритмов O(n). Это значит, что по мере увеличения количества элементов, n, алгоритмы O(n²), в конечном итоге потребуют больше времени, чем алгоритмы O(n). Это не значит, что алгоритмы O(n) всегда выполняются быстрее, чем алгоритмы O(n²), даже в одинаковом окружении на одинаковом оборудовании. Может быть так, что для небольших входных данных алгоритм O(n²) будет и в самом деле работать быстрее, однако, со временем, по мере увеличения размеров входных данных в сторону бесконечности, время исполнения алгоритма O(n²) будет в конце концов затмевать время исполнения алгоритма O(n). Также как и любая квадратичная математическая функция будет в конечном счёте обгонять любую линейную функцию. И не важно насколько велика фора у значения линейной функции в самом начале. Если вы работаете с большими объёмами данных, то алгоритмы, выполняющиеся за O(n²), в итоге замедляют вашу программу, но на небольших размерах входных данных вы этого даже не заметите, скорее всего. Ещё один вид асимптотической сложности -- это логарифмическое время, O(log n). Примером алгоритма, который выполняется так быстро, служит классический алгоритм двоичного поиска для нахождения элемента в предварительно отсортированном наборе. Если вы не знаете, как выполняется двоичный поиск, я сейчас быстренько всё объясню. Скажем, вы ищете число 3 в массиве целых чисел. Берём центральный элемент массива и спрашиваем: "Нужный мне элемент больше, меньше или равен этому?" Если равен -- отлично. Мы нашли нужный элемент, на этом всё. Если больше, то понятно, что наш элемент должен быть в массиве где-то справа, и дальше можно смотреть только в правую часть. Если меньше, тогда понятно, что элемент где-то слева. Затем повторяем этот процесс со всё более короткими массивами, пока не найдём нужный элемент. Этот мощный алгоритм уменьшает размер массива в два раза после каждой операции. То есть для нахождения элемента в отсортированном массиве длины 8 нужно не более (log₂8) или трёх таких операций проверки центрального элемента и выбора нужной половины. В то же время для массива длины 16 понадобится (log₂16) или четыре операции. А это всего одна дополнительная операция при удвоении длины массива. Удвоение размера увеличивает время исполнения всего на один кусок кода. Ещё раз -- проверяем центральный элемент и делим массив. Итак, это называют логарифмическое время, O(log n). Но погоди-ка, скажете вы, а не зависит ли он от того, где в массиве находится искомый элемент? Что если первый же элемент, который мы проверим окажется тем самым? Тогда это займёт всего одну операцию, и не важно насколько большой массив. Именно поэтому в информатике существуют ещё другие понятия для асимптотической сложности, которые отражают производительность в лучшем и худшем случае. Или более строго -- верхнюю и нижнюю границы времени исполнения алгоритма. В наилучшем случае для двоичного поиска наш элемент находится прямо тут -- в центре. Мы находим его за постоянное время вне зависимости от величины остального массива. Для этого используют символ Ω. То есть говорят, что алгоритм выполняется за Ω(1). В лучшем случае он находит элемент очень быстро. Не важно насколько большой массив. Но вот в худшем случае понадобится выполнить (log n) проверок и разделений массива, чтобы найти нужный элемент. Верхняя граница для худшего случая обозначается "большим О", как вы уже знаете. Таким образом получается O(log n), но Ω(1). Для сравнения линейный поиск, в котором мы просматриваем каждый элемент в массиве, чтобы найти нужный, в лучшем случае Ω(1). То есть снова первый элемент оказывается тем самым, что мы ищем. Поэтому не важно насколько большой у нас массив. В худшем случае искомый элемент находится в самом конце. И придётся пройти через все n элементов массива, чтобы его найти. Вот так, если мы ищем 3. То есть его время исполнения O(n), так как оно пропорционально числу элементов массива. Ещё используется символ Θ. С его помощью описываются алгоритмы, у которых лучшее и худшее время одинаковое. Как в случае алгоритма поиска длины строки, о котором мы говорили ранее. Того, где мы сохраняем длину в переменной заранее, а в последствии просто читаем её за постоянное время. Без разницы, какое именно число мы сохраняем в этой переменной, мы будем на него смотреть. В лучшем случае мы смотрим значение и получаем длину строки. То есть Ω(1) или постоянное время для лучшего случая. В худшем случае мы смотрим значение и получаем длину строки. То есть O(1) или постоянное время для худшего случая. Таким образом лучший и худший случаи одинаковые. И можно сказать, что алгоритм исполняется за время Θ(1). Подводя итог, у нас есть хорошие способы рассуждения об эффективности кода без выяснения того, сколько реального времени он потребует для выполнения. Такое время зависит от большого числа внешних факторов, таких как аппаратное и программное обеспечение, а также специфика самого кода. А ещё мы можем чётко рассуждать о том, что будет, когда размер входных данных возрастёт. Если у нас есть алгоритм O(n²), или ещё хуже алгоритм O(2ⁿ), то есть один из самых быстро возрастающих видов, тогда замедление действительно будет трудно не заметить при работе с увеличивающимися объёмами данных. Это и есть асимптотическая сложность. Спасибо за внимание.
История вопроса
Важность эффективности с упором на время исполнения подчёркивала Ада Лавлейс в 1843 по поводу механической аналитической машины Чарлза Бэббиджа :
«Почти во всех вычислениях возможен большой выбор конфигураций для успешного завершения процесса и различные соглашения должны влиять на выбор с целью выполнения вычислений. Существенная вещь - выбор конфигурации, котрая приведёт к минимизации времени, необходимого для выполнения вычисления» .
Ранние электронные компьютеры были очень ограничены как по скорости, так и по памяти. В некоторых случаях было осознано, что существует компромисс времени и памяти , при котором задача должна либо использовать большое количество памяти для достижения высокой скорости, либо использовать более медленный алгоритм, использующий небольшое количество рабочей памяти. В этом случае использовался наиболее быстрый алгоритм, для которого было достаточно имеющейся памяти.
Современные компьютеры много быстрее тех ранних компьютеров и имеют много больше памяти (гигабайты вместо килобайт). Тем не менее, Дональд Кнут подчёркивает, что эффективность остаётся важным фактором:
«В установившихся технических дисциплинах улучшение на 12% легко достижимо, никогда не считалось запредельным и я верю, что то же самое должно быть в программировании»
Обзор
Алгоритм считается эффективным, если потребляемый им ресурс (или стоимость ресурса) на уровне или ниже некоторого приемлемого уровня. Грубо говоря, «приемлемый» здесь означает «алгоритм будет работать умеренное время на доступном компьютере». Поскольку с 1950-х годов наблюдалось значительное увеличение вычислительной мощности и доступной памяти компьютеров, существующий «приемлемый уровень» не был приемлемым даже 10 лет назад.
Производители компьютеров периодично выпускают новые модели, зачастую более мощные . Стоимость программного обеспечения может быть достаточно велика, так что в некоторых случаях проще и дешевле для достижения лучшей производительности купить более быстрый компьютер, обеспечивающий совместимость с существующим компьютером.
Существует много путей измерения используемых алгоритмом ресурсов. Два наиболее используемых измерения - скорость и используемая память. Другие измерения могут включать скорость передачи, временное использование диска, долговременное использование диска, потребление энергии, совокупная стоимость владения , время отклика на внешние сигналы и так далее. Многие из этих измерений зависят от размера входных данных алгоритма (то есть от количеств требующих обработки данных). Измерения могут также зависеть от способа, в котором данные представлены (например, некоторые алгоритмы сортировки плохо работают на уже сортированных данных или когда данные отсортированы в обратном порядке).
На практике существуют и другие факторы, влияющие на эффективность алгоритма, такие как требуемая точность и/или надёжность. Как объяснено ниже, способ реализации алгоритма может также дать существенный эффект на фактическую эффективность, хотя многие аспекты реализации относятся к вопросам оптимизации.
Теоретический анализ
В теоретическом анализе алгоритмов обычной практикой является оценка сложности алгоритма в его асимптотическом поведении, то есть для отражения сложности алгоритма как функции от размера входа n используется нотация «O» большое . Эта оценка, в основном, достаточно точна при большом n , но может привести к неправильным выводам при малых значениях n (так, сортировка пузырьком, считающаяся медленной, может оказаться быстрее «быстрой сортировки», если нужно отсортировать лишь несколько элементов).
Некоторые примеры нотации «O» большое:
| Обозначение | Название | Примеры |
|---|---|---|
| O (1) {\displaystyle O(1)\,} | постоянное | Определение, чётно или нечётно число. Использование таблицы поиска постоянного размера. Использование подходящей хэш-функции для выбора элемента. |
| O (log n) {\displaystyle O(\log n)\,} | логарифмическое | Нахождение элемента в отсортированном массиве с помощью двоичного поиска или сбалансированного дерева , как и операции в биномиальной куче . |
| O (n) {\displaystyle O(n)\,} | линейное | Поиск элемента в несортированном списке или несбалансированном дереве (худший случай). Сложение двух n -битных чисел с использованием сквозного переноса . |
| O (n log n) {\displaystyle O(n\log n)\,} | квазилинейное , логарифмически линйное | Вычисление быстрого проеобразования Фурье , пирамидальная сортировка , быстрая сортировка (лучший и средний случай), сортировка слиянием |
| O (n 2) {\displaystyle O(n^{2})\,} | квадратное | Умножение двух n -значных чисел с помощью простого алгоритма, сортировка пузырьком (худший случай), сортировка Шелла , быстрая сортировка (худший случай), сортировка выбором , сортировка вставками |
| O (c n) , c > 1 {\displaystyle O(c^{n}),\;c>1} | экспоненциальное | Нахождение (точного) решения задачи коммивояжёра с помощью динамического программирования . Определение, не являются ли два логических утверждения эквивалентными с помощью полного перебора |
Проверочные испытания: измерение производительности
Для новых версий программного обеспечения или для обеспечения сравнения с соперничающими системами иногда используются тесты , позволяющие сравнить относительную производительность алгоритмов. Если, например, выпускается новый алгоритм сортировки , его можно сравнить с предшественниками чтобы убедиться, что алгоритм по меньшей мере столь же эффективен на известных данных, как и другие. Тесты производительности могут быть использованы пользователями для сравнения продуктов от различных производителей для оценки, какой продукт будет больше подходить под их требования в терминах функциональности и производительности.
Некоторые тесты производительности дают возможность проведения сравнительного анализа различных компилирующих и интерпретирующих языков, как например Roy Longbottom’s PC Benchmark Collection , а The Computer Language Benchmarks Game сравнивает производительность реализаций типичных задач в некоторых языках программирования.
Вопросы реализации
Вопросы реализации могут также повлиять на фактическую эффективность. Это касается выбора языка программирования и способа, каким алгоритм фактически закодирован, выбора транслятора для выбранного языка или используемых опций компилятора, и, даже, используемой операционной системы. В некоторых случаях язык, реализованный в виде интерпретатора , может оказаться существенно медленнее, чем язык, реализованный в виде компилятора
Есть и другие факторы, которые могут повлиять на время или используемую память, но которые оказываются вне контроля программиста. Сюда попадает выравнивание данных , детализация данных , сборка мусора , параллелизм на уровне команд и вызов подпрограмм .
Некоторые процессоры имеют способность выполнять векторные операции , что позволяет одной операцией обработать несколько операндов. Может оказаться просто или непросто использовать такие возможности на уровне программирования или компиляции. Алгоритмы, разработанные для последовательных вычислений могут потребовать полной переработки для использования параллельных вычислений .
Другая проблема может возникнуть с совместимостью процессоров, в которых команды могут быть реализованы по другому, так что команды на одних моделях могут быть относительно более медленными на других моделях. Это может оказаться проблемой для оптимизирующего компилятора.
Измерение использования ресурсов
Измерения обычно выражаются как функция от размера входа n .
Два наиболее важных измерения:
- Время : как долго алгоритм занимает процессор.
- Память : как много рабочей памяти (обычно RAM) нужно для алгоритма. Здесь есть два аспекта: количество памяти для кода и количество памяти для данных, с которыми код работает.
Для компьютеров, питающихся от батарей (например, лэптопов) или для очень длинных/больших вычислений (например, на суперкомпьютерах), представляют интерес измерения другого рода:
- Прямое потребление энергии : энергия, необходимая для работы компьютера.
- Косвенное потребление энергии : энергия, необходимая для охлаждения, освещения, и т.п.
В некоторых случаях нужны другие, менее распространённые измерения:
- Размер передачи : пропускная способность канала может оказаться ограничивающим фактором. Для уменьшения количества передаваемых данных можно использовать сжатие . Отображение рисунка или изображения (как, например, Google logo) может привести к передаче десятков тысяч байт (48K в данном случае). Сравните это с передачей шести байт в слове «Google».
- Внешняя память : память, необходимая на диске или другом устройстве внешней памяти. Эта память может использоваться для временного хранения или для будущего использования.
- Время отклика : параметр особенно важен для приложений, работающих в реальном времени, когда компьютер должен отвечать быстро на внешние события.
- Общая стоимость владения : параметр важен, когда предназначен для выполнения одного алгоритма.
Время
Теория
Этот вид тестов существенно зависит также от выбора языка программирования, компилятора и его опций, так что сравниваемые алгоритмы должны быть реализованы в одинаковых условиях.
Память
Этот раздел касается использования основной памяти (зачастую, RAM) нужной алгоритму. Как и для временно́го анализа выше, для анализа алгоритма обычно используется анализ пространственной сложности алгоритма , чтобы оценить необходимую память времени исполнения как функцию от размера входа. Результат обычно выражается в терминах «O» большое .
Существует четыре аспекта использования памяти:
- Количество памяти, необходимой для хранения кода алгоритма.
- Количество памяти, необходимое для входных данных.
- Количество памяти, необходимое для любых выходных данных (некоторые алгоритмы, такие как сортировки, часто переставляют входные данные и не требуют дополнительной памяти для выходных данных).
- Количество памяти, необходимое для вычислительного процесса во время вычислений (сюда входят именованные переменные и любое стековое пространство, необходимое для вызова подпрограмм, которое может быть существенным при использовании рекурсии).
Ранние электронные компьютеры и домашние компьютеры имели относительно малый объём рабочей памяти. Так, в 1949 EDSAC имел максимальную рабочую память 1024 17-битных слов, а в 1980 Sinclair ZX80 выпускался с 1024 байтами рабочей памяти.
Современные компьютеры могут иметь относительно большое количество памяти (возможно, гигабайты), так что сжатие используемой алгоритмом памяти в некоторое заданное количество памяти требуется меньше, чем ранее. Однако, существование трёх различных категорий памяти существенно:
- Кэш (часто, статическая RAM) – работает на скоростях, сравнимых с ЦПУ
- Основная физическая память (часто, динамическая RAM) – работает чуть медленнее ЦПУ
- Виртуальная память (зачастую, на диске) – даёт иллюзию огромной памяти, но работает в тысячи раз медленнее RAM.
Алгоритм, необходимая память которого укладывается в кэш компьютера, работает много быстрее, чем алгоритм, умещающийся в основную память, который, в свою очередь, будет много быстрее алгоритма, который использует виртуальное пространство. Усложняет ситуацию факт, что некоторые системы имеют до трёх уровней кэша. Различные системы имеют различное количество этих типов памяти, так что эффект памяти для алгоритма может существенно отличаться при переходе от одной системы к другой.
В ранние дни электронных вычислений, если алгоритм и его данные не помещались в основную память, он не мог использоваться. В наши дни использование виртуальной памяти обеспечивает огромную память, но за счёт производительности. Если алгоритм и его данные умещаются в кэш, можно получить очень высокую скорость, так что минимизация требуемой памяти помогает минимизировать время. Алгоритм, который не помещается полностью в кэш, но обеспечивает локальность ссылок может работать сравнительно быстро.
Алгоритм - набор инструкций, описывающих порядок действий исполнителя для достижения некоторого результата.
ВременнАя эффективность
является индикатором скорости работы алгоритма
оценивается по количеству основных операций, которые должен выполнить алгоритм при обработке входных данных размера n
Важен порядок роста времени выполнения алгоритма в зависимости от n
Пространственная эффективность показывает, сколько дополнительной оперативной памяти нужно для работы алгоритма. Эффективность оценивают в наихудшем, наилучшем и среднем случаях.
Виды анализа: математический и эмпирический
Измерение времени выполнения алгоритма
1. Непосредственное (эмпирический анализ)
2. Определение количества базовых операций, которые должен выполнить алгоритм при обработке входных данных размера n (математический анализ)
Порядок роста
При малых размерах входных данных невозможно заметить разницу во времени выполнения между эффективным и неэффективным алгоритмом. Для больших значений n вычисляют порядок роста функции.
Эффективность алгоритма в разных случаях
Существует большое количество алгоритмов, время выполнения которых зависит не только от размера входных данных, но и от конкретных особенностей входных данных (пример – поиск).
Эффективность измеряют для:
Пример: среднее количество операций сравнения при поиске:
Итак:
При разработке алгоритмов очень важно иметь возможность оценить ресурсы, необходимые для проведения вычислений, результатом оценки является функция сложности (трудоемкости). Оцениваемым ресурсом чаще всего является процессорное время (вычислительная сложность) и память (сложность алгоритма по памяти). Оценка позволяет предсказать время выполнения и сравнивать эффективность алгоритмов.
Библиотека программиста
«Если отладка - процесс удаления ошибок, то программирование должно быть процессом их внесения»
Э.Дейкстра
1.2. Зачем изучать алгоритмы? Эффективность алгоритмов
Во-первых, алгоритмы являются жизненно необходимыми составляющими для решения любых задач по различным направлениям компьютерных наук. Алгоритмы играют ключевую роль на современном этапе развития технологий. Здесь можно вспомнить такие распространенные задачи, как:
- решения математических уравнений различной сложности, нахождения произведения матриц, обратных матриц;
- нахождения оптимальных путей транспортировки товаров и людей;
- нахождения оптимальных вариантов распределения ресурсов между различными узлами (производителями, станками, работниками, процессорами и т.д.);
- нахождения в геноме последовательностей, которые совпадают;
- поиск информации в глобальной сети Интернет;
- принятия финансовых решений в электронной коммерции;
- обработка и анализ аудио и видео информации.
Этот список можно продолжать и продолжать и, собственно говоря, почти невозможно найти такую область компьютерных наук и информатики, где бы ни использовались те или иные алгоритмы.
Во-вторых, качественные и эффективные алгоритмы могут быть катализаторами прорывов в отраслях, которые являются на первый взгляд далеки от компьютерных наук (квантовая механика, экономика и финансы, теория эволюции).
И, в-третьих, изучение алгоритмов это также невероятно интересный процесс, который развивает наши математические способности и логическое мышление.
1.3. Эффективность алгоритмов
Предположим, быстродействие компьютера и объем его памяти можно увеличивать до бесконечности. Была бы тогда необходимость в изучении алгоритмов? Да, но только для того, чтобы продемонстрировать, что метод развязку имеет конечное время работы и что он дает правильный ответ. Если бы компьютеры были неограниченно быстрыми, подошел бы произвольный корректный метод решения задачи. Конечно, тогда чаще всего избирался бы метод, который легче реализовать.
Сегодня очень мощные компьютеры, но их быстродействие не является бесконечно большой, как и память. Таким образом, при исчислении - это такой же ограниченный ресурс, как и объем требуемой памяти. Этими ресурсами следует пользоваться разумно, чем и способствует применение алгоритмов, которые эффективны в плане использования ресурсов времени и памяти.
Алгоритмы, разработанные для решения одной и той же задачи, часто могут очень сильно отличаться по эффективности. Эти различия могут быть намного больше заметными, чем те, которые вызваны применением различного аппаратного и программного обеспечения.
Как отмечалось выше, в этом разделе центральную роль будет посвящено задачи сортировка. Первый алгоритм, который будет рассматриваться - сортировка включением, для своей работы требует времени, количество которого оценивается как c 1 n 2 , где n - размер входных данных (Количество элементов в последовательности для сортировки), c 1 - Некоторая постоянная. Это выражение указывает на то, как зависит время работы алгоритма от объема исходных данных. В случае сортировки включением эта зависимость является квадратичной. Второй алгоритм - сортировка слиянием - требует времени, количество которого оценивается как 2 nLog 2 n. Обычно константа сортировки включением меньше константы сортировки слиянием, то есть c12 растет быстрее с увеличением n, чем функция яLog 2 n. И для некоторого значения n = n 0 будет достигнуто такой момент, когда влияние разницы констант перестанет иметь значение и в дальнейшем функция c 2 nLog 2 n будет меньше c 1 n 2 для любых n > n 0 .
Для демонстрации этого рассмотрим два компьютера - А и Б. Компьютер А более быстрый и на нем работает алгоритм сортировки, а компьютер Б более медленный и на нем работает алгоритм сортировки методом слияния. Оба компьютера должны выполнить сортировку множества, состоит из миллиона чисел. Предположим, что компьютер А выполняет миллиард операций в секунду, а компьютер Б - лишь десять миллионов, есть А работает в 100 раз быстрее Б. Чтобы разница стала более ощутимой, допустим что код метода включения написан лучшим программистом в мире с использованием команд процессору, и для сортировки n чисел с этим алгоритмом нужно выполнить 2n 2 операций (то есть C 1 = 2). Сортировка методом слияния на компьютере Б написано программистом начинающим с использованием языка высокого уровня и полученный код требует 50nlog 2 n операций (то есть c 2 = 50). Таким образом, для сортировки миллиона чисел компьютеру А потребуется
а компьютеру Б -
Поэтому, использование кода, время работы которого растет медленнее, даже при плохом компьютере и плохом компиляторе требует на порядок меньше процессорного времени! Для сортировка 10000000 цифр преимущество сортировки слиянием становится еще более ощутимой: если сортировка включением требует для такой задачи примерно 2,3 дня, то для сортировка слиянием - меньше 20 минут. Общее правило таково: чем больше количество элементов для сортировки, тем заметнее преимущество сортировки слиянием. Приведенный выше пример демонстрирует, что алгоритмы, как и программное обеспечение компьютеру, представляют собой технологию . Общая производительность системы настолько же зависит от эффективности алгоритма, как и от мощности аппаратных средств.
Помимо проверки того, что алгоритм, реализованный школьником в качестве решения способен выдать правильный ответ задачи к при тех или иных исходных данных, при проверке решения также учитывается и время работы программы. Это не значит, то жизненно необходимо во всех без исключения задачах писать оптимальные алгоритмы (которые, зачастую могут отнять много времени на их грамотную реализацию и отладку). Это просто означает, что в некоторых отдельных задачах параметр времени может играть очень важную роль. Вполне может случиться, что на каком-нибудь олимпиадном туре вообще не будет ни одной задачи, в которой необходима оптимальность. Однако, может случиться и наоборот.
Таким образом и школьники, и преподаватели должны уметь сравнивать разные алгоритмы по их эффективности. Школьники - для того, чтобы выбрать в нужный момент наиболее подходящий способ решения задачи, преподаватели - чтобы грамотно подбирать задачи и понимать, какое решение подразумевал автор той или иной задачи, задавая именно такие ограничения по времени.
Для оценки эффективности алгоритма применяется функция сложности, обозначаемая O (читается «о большое»). На самом деле есть и другие оценки, но на этапе когда школьник только-только начинает знакомиться с различными алгоритмами они не очень нужны. Функция сложности отражает по какой закономерности будет расти время выполнения программы в зависимости от исходных данных или их количества.
В качестве примера алгоритма, время выполнения которого зависит от исходного данного - алгоритм нахождения всех натуральных делителей числа N. Очевидно, что чем больше число, тем больше шагов цикла будет необходимо сделать. Примером алгоритма, время выполнения которого зависит от количества входных данных будет поиск наибольшего числа в массиве. Чем длиннее массив, тем больше операций сравнения необходимо сделать, чтобы определить какое число является наибольшим.
Основными функциями являются:
l O(1) - такая функция сложности говорит о том, что время работы программы постоянно при любых исходных данных;
l O(N) - количество операций растет пропорционально N (здесь N может быть как параметром задачи, так и количеством элементов в массиве).
l O(log N) - количество операций растет пропорционально логарифму N (именно такой сложностью обладает, например, метод половинного деления при поиске элемента в упорядоченном массиве). При увеличении N на порядок количество операций меняется на единицу. Основание логарифма обычно не уточняется, нас интересует характер роста (быстро/медленно), а не точное значение времени.
l O(N2) - количество операций растет пропорционально квадрату N. В общем случае может быть O(Nk) в зависимости от сложности задачи.
l O(N!) - количество операций растет пропорционально факториалу N.
Здесь существует некоторое количество тонкостей, связанных с тем что не все операции выполняются за одинаковое время, поэтому при оценке временной сложности используются те операции, которые требуют наибольшего времени.
Чаще всего при описании алгоритмов приводится оценка времени их работы в чистом виде, то есть без учета операций ввода/вывода.
Пример: оценим сложность программы, вводящей с клавиатуры массив и находящей в нем наибольший элемент.
Сложим количество операций N+(N-1)+1=2N. То есть существует такая константа, что при любом N количество операций не превышает CN. Следовательно, сложность алгоритма равна O(N).
Пример: оценим сложность программы, вводящей с клавиатуры массив и находящей в нем элемент с заданным свойством (например, равный определенному значению).
Алгоритм состоит из следующих шагов:
Ввод массива (N операций ввода) поиск элемента с заданным свойством (как повезет: элемент может находиться как ближе к началу массива, так и в самом конце; если элемента не существует, то необходимо сделать все N сравнений, чтобы в этом убедиться) вывод результата.
В лучшем случае данный алгоритм потребует N+2 операции (ввод всего массива, единственное сравнение, вывод), в худшем (когда такого элемента нет - 2N+1 операцию). Если N будет большим числом, к примеру порядка 106, то единицей можно пренебречь. Следовательно, сложность алгоритма равна O(N).
Пример: определим функцию сложности алгоритма шифрования слова, длины L методом подстановки. Пусть существует таблица, в которой для каждого символа алфавита записан символ, на который его надо заменить. Обозначим количество букв алфавита S.
Алгоритм состоит из следующих шагов:
Ввод слова (одна операция) цикл по всем символам
1. для каждого символа найти его замену в таблице (если таблица не упорядочена и не обладает какими-нибудь свойствами, облегчающими поиск, то в худшем случае S операций для одного символа, если искомый элемент находится в самом конце)
2. вывод найденного символа
Конец цикла
Общее количество операций 1+(S+1)*L. В случае достаточно больших S и L единицами можно пренебречь, получится что функция сложности данного алгоритма есть O(S*L).
Пример: определим функцию сложности алгоритма перевода натурального числа N в двоичную систему счисления (без операций ввода и вывода данных).
Алгоритм состоит из следующих шагов:
Цикл, пока результат деления числа на 2 не станет равным 0
1. разделить число на 2 и запомнить остаток
2. принять результат деления за новое число
Конец цикла
Общее количество операций не превышает 1+log2N. Поэтому данный алгоритм имеет сложность O(log N).
Если программа состоит из нескольких частей с различными функциями сложности, то бо льшая функция сложности «поглотит» меньшие. Например, если делается ввод массива O(N), сортировка O(N2) и вывод упорядоченного массива за O(N), то можно сказать, что вся программа имеет сложность O(N2)
Практическое применение знаний о функиях сложности алгоритмов двояко. Во-первых, для какой-то задачи можно выбрать более оптимальный алгоритм, если о нем есть соответствующие данные в литературе. Во-вторых, зная время работы своего решения на одном наборе исходных данных, школьник может примерно прикинуть время работы этой же программы на данных, которые соответствуют максимальным ограничениям по данной задаче.
Вопросы
Данные задачи служат для самопроверки по изложенному материалу и не являются обязательными.
1. Определите функцию сложности алгоритма решения квадратного уравнения.
2. Определите фукцию сложности алгоритма рисования правильного многоугольника по заданному количеству сторон.
3. Определите функцию сложности алгоритма вставки элемента в массив на заданную позицию (со предварительным смещением всех элементов с номерами большими либо равными данному на одну позицию вправо).
4. Определите функцию сложности алгоритма сложения двух натуральных чисел в столбик (пусть A - количество цифр первого числа, B - количество цифр второго).
5. Определите функцию сложности алгоритма умножения двух натуральных чисел в столбик.
