 |
АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция
Нотация О-большого
|
Читайте также: |
«О-большое» обеспечивает хороший способ сравнения алгоритмов по времени выполнения. В асимптотическом анализе использование «О-большое», позволяет обратиться к показателю степени или самому доминирующему показателю.
Самое важное свойство «О-большое» то, что оно позволяет игнорировать константы и степень низшего порядка.
500n3 + 10n2 + 17n + 121345 = O (n3)
Пример 2 Использование «О-большое»
В вышеупомянутом примере самый высокий показатель порядка в уравнении времени выполнения 500n3. Проигнорируем константу и степень низшего порядка в этом показателе и примем, что время выполнения O (n3).
Большинство алгоритмов, с которыми приходится встречается, попадает в один из следующих классов.
· O(1) – constant time
· O(log(n)) – logarithmic time
· O(n) – linear time
· O(n log(n)) – "n-log-n" time
· O(n2) – quadratic time
· O(n3) – cubic time
· O(2n) – exponential time
Алгоритмы, у которых есть время выполнения O(n log(n)) очень хорошо применимы к большим проблемным экземплярам. Квадратные и кубические алгоритмы показывают однозначно худшую производительность, особенно для случаев, когда ввод становится большим. Наконец, экспоненциальные алгоритмы рекомендуется использовать только для очень маленьких вводов.
Важно выразить логическое время выполнения с точки зрения физического времени, используя секунды, минуты, часы, и т.д получить понимание того, что действительно означают эти характеристики. Во-первых, давайте рассмотрим O(n log(n)) алгоритм, который занимает 1 секунду при вводе размера 1000.
| input size | running time |
| 1 second | |
| 2.2 seconds | |
| 6.2 seconds | |
| 13.3 seconds | |
| 2.77 minutes | |
| 106 | 33.3 minutes |
| 107 | 6.48 hours |
Таблица 1 O(n log(n)) алгоритм
В сравнении, вот квадратный алгоритм, который также занимает 1 секунду на вводе размера 1000.
| input size | running time |
| 1 second | |
| 4 seconds | |
| 25 seconds | |
| 1.66 minutes | |
| 2.77 hours | |
| 106 | 11.5 days |
| 107 | 3.25 years |
Таблица 2 O (n2) алгоритм
Для очень больших вводов размера десять миллионов, квадратный алгоритм становится полностью бесполезным. Даже для одного миллиона он уже может быть бесполезным: если, допустим рассматривается некоторая система банковской бухгалтерии, которая должна обновляться ежедневно. С другой стороны, квадратная производительность достаточно хороша при сравнении с экспоненциальным временем выполнения. Чтобы видеть насколько катастрофично экспоненциальное время выполнения, рассмотрим экспоненциальный алгоритм который занимает 1 секунду при вводе размера 10. Для этой ситуации получим приблизительно следующее время для больших экземпляров.
| input size | running time |
| 1 seconds | |
| 32 seconds | |
| 17.1 minutes | |
| 9.1 hours | |
| 12.1 days | |
| 1.09 years | |
| 34.9 years | |
| 35700 years | |
| 4.02 1019 years |
Таблица 3 O (2n) алгоритм
Последнее число даже превышает возраст вселенной (приблизительно 15 x 109 годы), и алгоритм уже бесполезно при вводах размера 30. У нас только есть приемлемая производительность до размера 25 или около этого. Таким образом, в некотором смысле, экспоненциальный алгоритм почти столь же плох как никакой алгоритм вообще.
К сожалению, есть некоторые известные вычислительные проблемы, которые, кажется, требуют экспоненциального времени выполнения. Обнаружение, Булева ли схема с n вводами могут когда-либо приводить к истине, поскольку вывод является одним из них: есть 2n возможные входные комбинации, и никак более нельзя упростить вычисление.
Поиск по сайту: