Асимптотическая сложность алгоритма

Материал из Неолурк, народный Lurkmore
Перейти к навигации Перейти к поиску
Количество операций для алгоритмов разной сложности

Асимптотическая сложность алгоритма — способ оценки вычислительной сложности алгоритма «с точностью до константы», применяемый в теории сложности. Обычно записывается в нотации «большого О».

Широко применяется, так как точная оценка сложности в элементарных операциях часто сложна (в том числе зависит и от того, что принять за элементарную операцию — одно действие в конкретном языке программирования, процессорный такт), а также не имеет смысла при больших объемах входных данных, когда медленнорастущие части временной функции практически перестают влиять на общий объем исполняемой работы.

Чаще всего используется асимптотическая оценка времени работы алгоритма сверху, записываемая как O(f(n)), где n — объем входных данных. Если принять функцию времени работы алгоритма в зависимости от объема входных данных как F(n), то можно сказать, что начиная с определенного числа N для всех n > N выполняется неравенство |F(n)| <= |N*f(n)|, иными словами, с некоторого момента функция F(n) растет не быстрее, чем N*f(n), где N — константа.

Оценки сложности алгоритмов:

  • Логарифмическая сложность — зависит от входных данных n как N*log(n), в частности, таковую сложность имеет операция поиска в индексированном массиве, быстрого возведения в произвольную степень. На практике чаще встречается сложность N*n*log(n).
  • Полиномиальная сложность — зависит от входных данных n как N*n^c, где c — некая конкретная степень. Указывается только старшая степень полинома, так как с ростом n меньшие степени перестают существенно влиять. Например, двойной перебор массива имеет сложность O(n²), реализация метода Шульце для n кандидатов — O(n³).
  • Экспоненциальная сложность — зависит от входных данных n как N*e^n. Использования алгоритмов с такой сложностью стараются избегать, это сложные задачи на графах, сложные операции поиска по нескольким таблицам в MySQL и т. д.

Возможны и более высокие сложности, например N*n!.

Eipi10.gif Хехехеххехехе. Пожилой математик одобряет
НаукиКакоцентризмЛогика (Второй семестр) • О сути познанияДилемма СкаибыАльберт ЭйнштейнМожет ли ёжик выжить на Луне?Технологический ВавилонВысшая математикаФизикаЕвгеникаМатанРоссийскаяСопроматСтатистикаФилософия (Детерминизм) • Бремя доказыванияЗнатствоМногие знания, многие печалиПритча про слепых и слонаБиологияПердун и ворВ глубине науки скрывается богословиеОсновной вопрос философииРастения — совершенная форма жизниКонцепция взаимоотношений полов Жоры РевазоваРусская наука vs западная наука2 + 2 = 4НаукаЦвета не существуетЗаклинатель говнаКладбище вероятностейЧисла, кратные 7Если в космосе нет воздуха, то как тогда горит СолнцеДеление многочлена (полинома) на многочленМажорантаDesmosУравнение ИмперииВладимир АрнольдСтремление к бесконечностиАсимптотическая сложность алгоритмаМаксим СолохинЯдерная трансмутация1864МракобесиеЛекция (Зелёный слоник)Это знать надо! Это классика!Научные мемы
ТеорииКластерPizdaАнализДоказательствоПро суть НТППочему существует нечто, а не ничтоТорнадо на свалкеСциентизм vs наукаЗемля станет черной дырой из-за микросхемFictional googologyКривая распределения IQЭффект ПьюдипаяДоктор СаржаПродажа 20 долларов дороже номиналаСила не в Ньютонах, сила в питонахСила не в Ньютонах, сила в АнтонахЭмпиризмФилософия наукиНатуропатияПатриотический Библейский университетПаранормальное явлениеПарапсихологияЭкспериментальный контрольЭкспериментДвойная шторкаПсевдоисторияПрофессор ДэйвКаково быть летучей мышьюНестор ГаврасАнтиидеяПризыв к милосердиюПричинно-следственная связьСергей ГредескулПчелиная индукцияПрофессор БатуринБетоноворотчикиРжавый БогУтиный тестТефлонGrokboxStarbasePer capitaПроизводствоТреугольник СерпинскогоСверхапостольныйПрофанское восприятие чертей и бесовПулинатГонорий ФиванскийПрофессор КутузовскийЛичность — иллюзияЭффекты первого, второго и третьего порядков
ДостиженияTeXАтомная бомбаБиореакторБольшой адронный коллайдерГМОДвести двадцатьКорчевательКубик РубикаНанотехнологииПалата мер и весовРезонатор ГельмгольцаРоботыТермоядерный синтезЧернобыльЭкзоскелетФукусимаФракталРулерЦиркульMp3256МозгИзенареллаСверхпроводникиКвантовый интернетДНК-тестКристаллУгольник (Угол) • КвалиаБессознательноеИзобретательПустое множествоИскания под фонарёмДрожжиCRCЕстественное правоНатурфилософияБытиеИдеализмМатерияСинхронистичностьСилаАнтинарремыЭкзистенциальный кризисКошачья логикаИдеализацияИзолентаНордическая теорияОтрицательная селекцияКонсеквенциализмТеория вероятностейАльтернативная энергетикаГрафологияХимияГеологияМысльСтруктураВеществаПсихиатрияРобот
ХитроеТысячеричная система счисленияЦепура ТульскогоТеплородСовершенственная национальная политикаЭнциклопедия БританникаМатричный мирЖивые камниГенри ФордКонстанта ХаосаКонстанта ПрекращенияРазрушительная теорияМостНанонавозИзобретать велосипедВойна токовФактДостижения ЕгиптаЛоренцево сокращениеЛюди произошли от червяГенетикаПрофессор ничегонеделанияРефлексияИнформацияВедический креационизмРукотворные ужасы за гранью вашего пониманияЕликсей ЛесликовПодгонианАкло СаваофСемиотикаВесьма нестандартные методыДиаграмма ОфитовХранитель традицийМногочленСамоотсылкаНезнание того, сколько будет 7 × 8Нарисуй параллелограммПолосы МахаПарето-оптимальностьПрогнозВечностьКвантовая точкаОбъект-771ЛучИскусственное сооружениеАверсия потериСотериология
ОткрытияГеометрия ЛобачевскогоЗвездчатый многоугольникКвантовая механикаКогнитивная психологияПопуляционная теория МальтусаРадиацияТёмная энергияТеория большого взрыва (сериалБольшой взрыв — антинаучен) • Теория относительностиТеория разбитых оконТеория струнЧетвёртое измерениеЧёрная дыраЭволюцияЭлементарные частицыЭнтропияЛюбительская астрономияОтношенияЗадачи с недостатком информацииГомбокНеосвещаемая комнатаМногомерные фигурыИсторияМежконтинентальная баллистическая ракетаOutside InЧёрный лебедьРептильный мозгТрансжирыБуриданов осёлНепрерывность сознанияКока-кола и МентосКвантовое бессмертиеВычисление длины акулы по её зубуФундаментальная проблема материализмаИнтерференцияИсхождениеЧистый листНеапокалиптические сценарии будущегоИстины не существуетЦепь МарковаЗадача ДидоныИндекс ХиршаНобелевская премияЭндорфинКалькулятор95 тезисов против эволюцииВопрос эволюции! КампанияЭволюционный синдромДебаты о происхожденииРедукционизмАбиогенезПанспермияЗадачи тысячелетияТеория МорозоваГомункулMG 42Философия отгороженностиБиологическая таксономияКогнитивная угрозаНарративная угрозаРазум это не мозгСвидетельства Всемирного ПотопаБыл ли Ноев КовчегУниформизмConway’s Game of LifeКлеточный автоматГосударство как организмНа ноль делить нельзяОткрытый разумОхотники за привидениями (телешоу)Инь и Ян
Люди и организацииИзябретательИлон МаскЯрослав ЗолотарёвГермес ТриждывеличайшийОлег Рыбаченко • Организации (ИТМОМФТИНМУ) • БайронБелоненкоБерезовскийВассерманВербицкийда ВинчиДекартДокинзИнженерКэрроллЛабораторияЛейбницЛуговский (цитатник) • Паскаль • Перельманы (ГригорийЯков) • ПереслегинПятисемитыСаганТейлорТеслаТехнофашистыФейнманХайямХокингЭшерАндрей КурпатовРоджер ПенроузWolfram AlphaАлександр ПушнойСергей ХачатуровЭхнатонАрсений ЯценюкКульт СингулярностиАрхивариусЖак Ив КустоПрофессор БагировNautilus LiveShark-ReferencesИван ИльинЦЕРНОлег ЗаморинПрофессорРоберт БойльАнаксагорАнаксимандрАнаксимен МилетскийПифагорДемокритФалес МилетскийСократПлатонАристотельЗенонАрхимедЭратосфенГиппократ ГераклидовичПарменидГераклитМайкл БихиДиогенИндуистский университет АмерикиПифагорская школаГеорг ГегельPathofMatthГеоргий ГурджиевАрсен МаркарянПлоскоземельщикиАлан ТьюрингГад СаадАртур ШопенгауэрЖан-Анри ФабрМихаил Лидин