Методи сортування
N)
0(1)
У алгоритмах константної складності більшість операцій| в програмі виконуються один або кілька разів. Будь-який алгоритм, що завжди вимагає незалежно від розміру даних одного| і того ж часу, має константну складність.
Час роботи програми лінійний, зазвичай|звично| коли кожен елемент вхідних даних потрібно обробити лише лінійне число разів.
0(N2), 0(N3), 0(Na)
Поліноміальна складність. 0(N2) — квадратична складність, 0(N3) — кубічна складність
0(Log|(N))
Коли час роботи програми логарифмічний, програма зачинає працювати набагато повільніше із збільшенням N. Такий час роботи зустрічається зазвичай в програмах, які ділять велику проблему на маленьких і вирішують їх окремо.
0(N*log|(N))
Такий час роботи мають ті алгоритми, які ділять велику проблему на маленьких, а потім, вирішивши їх, сполучають|з'єднують|
їх рішення|вирішення|.
0(2N)
Експоненціальна складність. Такі алгоритми найчастіше виникають в результаті підходу, що іменується методом грубої сили.
Впорядкування елементів безлічі|множини| в зростаючому або спадаючому порядку|ладі| називається сортуванням.
З|із| впорядкованими елементами простіше працювати, чим з|із| хаотично| розташованими|схильними|: легко знайти необхідні елементи, виключити, вставити нові. Сортування застосовується при трансляції| програм, при організації наборів даних на зовнішніх носіях, при створенні|створінні| бібліотек, каталогів, баз даних і так далі
Алгоритми сортування можна розбити на наступні|такі| групи (мал. 2.1).
Зазвичай сортовані елементи безлічі називають записами і позначають через k1, k2 ..., кn.