Методи сортування

N)

0(1)

У алгоритмах константної складності більшість опера­цій| в програмі виконуються один або кілька разів. Будь-який алгоритм, що завжди вимагає незалежно від розміру даних од­ного| і того ж часу, має константну складність.

Час роботи програми лінійний, зазвичай|звично| коли кожен елемент вхідних даних потрібно обробити лише лінійне число разів.

0(N²), 0(N³), 0(N^a)

Поліноміальна складність. 0(N²) — квадратична складність, 0(N³) — кубічна складність

0(Log|(N))

Коли час роботи програми логарифмічний, програма зачинає працювати набагато повільніше із збільшенням N. Такий час роботи зустрічається зазвичай в програмах, які ділять велику проблему на маленьких і вирішують їх окремо.

0(N*log|(N))

Такий час роботи мають ті алгоритми, які ділять велику проблему на маленьких, а потім, вирішивши їх, сполучають|з'єднують|

їх рішення|вирішення|.

0(2^N)

Експоненціальна складність. Такі алгоритми найчастіше виникають в результаті підходу, що іменується методом грубої сили.

Впорядкування елементів безлічі|множини| в зростаючому або спадаючому порядку|ладі| називається сортуванням.

З|із| впорядкованими елементами простіше працювати, чим з|із| хаотично| розташованими|схильними|: легко знайти необхідні елементи, виключити, вставити нові. Сортування застосовується при транс­ляції| програм, при організації наборів даних на зовнішніх носіях, при створенні|створінні| бібліотек, каталогів, баз даних і так далі

Алгоритми сортування можна розбити на наступні|такі| групи (мал. 2.1).

Зазвичай сортовані елементи безлічі називають записами і позначають через k₁, k₂ ..., к_n.