Как да се направи оценка на сложността на алгоритъма - концепцията за сложността на алгоритъма - концепцията на алгоритъма - каталогът файлове

Анализ на скорост на изпълнение алгоритъм

Има няколко начина за измерване на сложността на алгоритъма. Програмистите обикновено се фокусира върху скоростта на алгоритъма, но не по-малко важно, както и други показатели - на изискванията за размера на паметта, диска. Използването на бърз алгоритъм няма да доведе до очакваните резултати, ако работата му ще се нуждаят от повече памет, отколкото на компютъра има.

Memory или време

Много алгоритми предлагат избор между капацитета на паметта и скоростта. Проблемът може да бъде решен бързо, като се използва голямо количество памет, или по-бавно, заема по-малко обем.

Типичен пример в този случай е най-краткият път за търсене на алгоритъм. Представяйки града като мрежова карта, е възможно да се напише алгоритъм за определяне на най-късото разстояние между всеки две точки на мрежата. Не за да се изчисли разстоянието, когато имаме нужда от тях, можем да извлечем най-кратките разстояния между всички точки и запишете резултатите в таблицата. Когато ние трябва да намерим най-късото разстояние между две точки, ние можем просто да отнеме от масата готов.

Резултатът ще бъде получена веднага, но това ще изисква огромно количество памет. Карта на големия град може да съдържа десетки хиляди точки. След това, по-горе описаната таблица трябва да съдържа повече от 10 милиарда. Cells. Т.е. с цел да се подобри ефективността на алгоритъма, допълнителни 10 GB памет, за да се използва.

От това идва идеята за зависимост от обема време сложност. При този подход, алгоритъмът се оценява, както по отношение на скоростта на изпълнение, и от гледна точка на памет, консумирани.

Проблемите олимпиада винаги има информация за максималния период от време, преминавайки през всички тестове, за да се провери ефективността на алгоритъма на програмата.

Подреждане на сложност на алгоритъма

При сравняване на различни алгоритми, е важно да се знае как тяхната сложност зависи от количеството на входните данни. Да кажем, ако нещо чрез преработка на хиляда номера отнема 1s и да се справят милиони номера - 10-секундното, чрез различен алгоритъм може да изисква 2в и 5в, съответно. При тези обстоятелства, не е възможно да се каже със сигурност какво алгоритъм по-добре.

Като цяло, от сложността на алгоритъма може да се определи в порядък. Алгоритъмът има сложност O (е (п)), ако увеличението на измерение N. време за изпълнение на входно увеличава алгоритъм със същата скорост като F функция (п). Разглеждане на код, който за матрица А [N х N] е максималната елемент във всеки ред.

ако А [Ь, й]> макс тогава

В този алгоритъм, променлива и варира от 1 до N. При всяка промяна аз. променлива й също се променя от 1 до N. В един от N повторения на външния контур, вътрешният контур се извършва N пъти, също. Общият брой на вътрешните повторения линия е равно на N х N. Това определя сложността на алгоритъм O (N2).

Оценка от порядъка на сложност на алгоритъма, трябва да ползвате само частта, която расте най-бързо. Да приемем, че работен цикъл е описан от експресията N 3 + N. В този случай, сложността е равна О (N 3). При изчисляване не може да се вземе предвид постоянните фактори в изрази. работен етап Алгоритъм 3 N 3 счита О (N 3). Това прави зависимостта на O (N) от промени в размера на проблема по-очевидна.

Как да се направи оценка на сложността на алгоритъма