Типы сооружений для обработки осадков: Септиками называются сооружения, в которых одновременно происходят осветление сточной жидкости...
Индивидуальные и групповые автопоилки: для животных. Схемы и конструкции...
Топ:
Характеристика АТП и сварочно-жестяницкого участка: Транспорт в настоящее время является одной из важнейших отраслей народного хозяйства...
Генеалогическое древо Султанов Османской империи: Османские правители, вначале, будучи еще бейлербеями Анатолии, женились на дочерях византийских императоров...
Выпускная квалификационная работа: Основная часть ВКР, как правило, состоит из двух-трех глав, каждая из которых, в свою очередь...
Интересное:
Как мы говорим и как мы слушаем: общение можно сравнить с огромным зонтиком, под которым скрыто все...
Отражение на счетах бухгалтерского учета процесса приобретения: Процесс заготовления представляет систему экономических событий, включающих приобретение организацией у поставщиков сырья...
Подходы к решению темы фильма: Существует три основных типа исторического фильма, имеющих между собой много общего...
Дисциплины:
2021-12-07 | 15 |
5.00
из
|
Заказать работу |
|
|
Оценка с точностью до порядка дает верхний предел сложности алгоритма. То, что программа имеет определенный порядок сложности, не означает, что алгоритм будет действительно выполняться так долго. При определенных исходных данных, многие алгоритмы выполняются гораздо быстрее, чем можно предположить на основании их порядка сложности. Например, следующий код реализует простой алгоритм выбора элемента из списка:
Function LocateItem(target As Integer) As Integer
For I = 1 To N
If Value(I) = target Then Exit For
Next I
LocateItem = I
End Sub
Если искомый элемент находится в конце списка, придется перебрать все N элементов для того, чтобы его найти. Это займет N шагов, значит сложность алгоритма порядка O(N). В этом, так называемом наихудшем случае (worst case) время выполнения алгоритма будет наибольшим.
С другой стороны, если искомое число в начале списка, алгоритм завершит работу практически сразу, совершив всего несколько итераций. Это так называемый наилучший случай (best case) со сложностью порядка O(1). Обычно и наилучший, и наихудший случаи встречаются относительно редко, и интерес представляет оценка усредненного или ожидаемого (expected case) поведения.
Если первоначально числа в списке распределены случайно, искомый элемент может оказаться в любом месте списка. В среднем потребуется проверить N/2 элементов для того, чтобы его найти. Значит, сложность этого алгоритма в усредненном случае порядка O(N/2), или O(N), если убрать постоянный множитель.
Для некоторых алгоритмов порядок сложности для наихудшего и наилучшего вариантов различается. Например, сложность алгоритма быстрой сортировки из 9 главы в наихудшем случае порядка O(N2), но в среднем его сложность порядка O(N*log(N)), что намного быстрее. Иногда алгоритмы типа быстрой сортировки бывают очень длинными, чтобы наихудший случай достигался крайне редко.
|
Часто встречающиеся функции оценки порядка сложности
В табл. 1.2 приведены некоторые функции, которые обычно встречаются при оценке сложности алгоритмов. Функции приведены в порядке возрастания вычислительной сложности сверху вниз. Это значит, что алгоритмы со сложностью порядка функций, расположенных вверху таблицы, будут выполняться быстрее, чем те, сложность которых определяется функциями из нижней части таблицы.
@Таблица 1.2. Часто встречающиеся функции оценки порядка сложности
Сложность алгоритма, определяемая уравнением, которое представляет собой сумму функций из таблицы, будет сводиться к сложности той из функций, которая расположена в таблице ниже. Например, O(log(N)+N2) — это то же самое, что и O(N2).
Обычно алгоритмы со сложностью порядка N*log(N) и менее сложных функций выполняются очень быстро. Алгоритмы порядка NC при малых C, например N2 выполняются достаточно быстро. Вычислительная же сложность алгоритмов, порядок которых определяется функциями CN или N! очень велика и эти алгоритмы пригодны только для решения задач с небольшим N.
В качестве примера в табл. 1.3 показано, как долго компьютер, выполняющий миллион инструкций в секунду, будет выполнять некоторые медленные алгоритмы. Из таблицы видно, что при сложности порядка O(CN) могут быть решены только небольшие задачи, и еще меньше параметр N может быть для задач со сложностью порядка O(N!). Для решения задачи порядка O(N!) при N=24 потребовалось бы время, большее, чем время существования вселенной.
Логарифмы
Перед тем, как продолжить дальше, следует остановиться на логарифмах, так как они играют важную роль в различных алгоритмах. Логарифм числа N по основанию B это степень P, в которую надо возвести основание, чтобы получить N, то есть BP=N. Например, если 23=8, то соответственно log2(8)=3.
|
@Таблица 1.3. Время выполнения сложных алгоритмов
Можно привести логарифм к другому основанию при помощи соотношения logB(N)=logC(N)/logC(B). Например, чтобы вычислить логарифм числа по основанию 10, зная его логарифм по основанию 2, можно воспользоваться формулой log10(N)=log2(N)/log2(10). При этом log2(10) — это табличная константа, примерно равная 3,32. Так как постоянные множители при оценке сложности алгоритма можно опустить, то O(log2(N)) — это же самое, что и O(log10(N)) или O(logB(N)) для любого B. Поскольку основание логарифма не имеет значения, часто просто пишут, что сложность алгоритма порядка O(log(N)).
В программировании часто встречаются логарифмы по основанию 2, что обусловлено применяемой в компьютерах двоичной системой исчисления. Поэтому мы для упрощения выражений будем везде писать log(N), подразумевая под этим log2(N). Если используется другое основание алгоритма, это будет обозначено особо.
|
|
Историки об Елизавете Петровне: Елизавета попала между двумя встречными культурными течениями, воспитывалась среди новых европейских веяний и преданий...
Общие условия выбора системы дренажа: Система дренажа выбирается в зависимости от характера защищаемого...
История развития пистолетов-пулеметов: Предпосылкой для возникновения пистолетов-пулеметов послужила давняя тенденция тяготения винтовок...
Семя – орган полового размножения и расселения растений: наружи у семян имеется плотный покров – кожура...
© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!