Алгоритми "разделяй и владей"

Двата алгоритъма за сортиране, които разгледахме досега, сортиране чрез пряка селекция (selection sort) и сортиране чрез вмъкване (insertion sort), имат най-лошо време за изпълнение $\Theta(n^2)$\Theta, left parenthesis, n, squared, right parenthesis. Когато размерът на входния масив е голям, изпълнението на тези алгоритми може да отнеме много време. В този и в следващия урок ще разгледаме други два алгоритъма за сортиране, сортиране чрез сливане (merge sort) и бързо сортиране (quick sort), които имат по-добро време за изпълнение. По-конкретно, сортиране чрез сливане се изпълнява за време $\Theta(n \lg n)$\Theta, left parenthesis, n, \lg, n, right parenthesis във всички случаи, а бързото сортиране се изпълнява за време $\Theta(n \lg n)$\Theta, left parenthesis, n, \lg, n, right parenthesis в най-добрия случай, а времето за изпълнение в най-лошия случай е $\Theta(n^2)$\Theta, left parenthesis, n, squared, right parenthesis. На таблицата са представени четирите алгоритъма със съответното им време за изпълнение:

И двата алгоритъма споделят обща алгоритмична парадигма, базирана на рекурсия. Тази парадигма, наречена разделяй и владей разделя задачата на подзадачи, които са подобни на първоначалната задача, решава ги рекурентно и накрая комбинира решението, за да реши първоначалната задача. Тъй като "разделяй и владей" решава подзадачите рекурентно, всяка подзадача трябва да е по-малка от първоначалната задача и трябва да има базов случай за всяка подзадача. Алгоритъмът "разделяй и владей" може да се раздели на 3 части:

Можеш лесно да запомниш стъпките на алгоритъма "разделяй и владей", като разделяй, владей, комбинирай. Ето как можем да представим една стъпка, като приемем, че всяка стъпка на разделяне създава две подзадачи (макар че някои алгоритми "разделяй и владей" могат да създадат повече от две):

Ако разширим с още две рекурентни стъпки, ще изглежда така:

Тъй като алгоритъмът "разделяй и владей" създава поне две подзадачи, този алгоритъм прави няколко рекурентни извиквания.

Това съдържание е резултат от съвместната дейност на преподавателите по Компютърни науки в Дартмут Thomas Cormen и Devin Balkcom, както и на екипа по компютърни науки на Кан Академия. Съдържанието е лицензирано CC-BY-NC-SA.