If you're seeing this message, it means we're having trouble loading external resources on our website.

Ако си зад уеб филтър, моля, увери се, че домейните *. kastatic.org и *. kasandbox.org са разрешени.

Основно съдържание

Компютърни науки

Курс: Компютърни науки > Раздел 1

Урок 8: Сортиране чрез сливане
Информатика
Компютърни науки
Алгоритми
Сортиране чрез сливане
© 2023 Khan AcademyУсловия за ползванеДекларация за поверителностПолитика за Бисквитки

Анализ на сортиране чрез сливане

Класна стая на Google
Ако ни е дадено, че функцията merge се изпълнява за Θ(n) време при сливането на n елемента, как ще покажем, че mergeSort се изпълнява за време Θ(nlog2⁡n)? Ще започнем, като си спомним за трите части на "разделяй и владей" и как да обясним техните времена за изпълнение. Ще предположим, че сортираме общо n елемента за целия масив.
  1. Стъпката "разделяй" отнема едно и също време без значение от размера на подмасива. В крайна сметка тази стъпка просто изчислява средната точка q на индексите p и r. Припомни си, че в нотацията big-Θ указваме константно време с Θ(1).
  2. Стъпката "владей", в която двата подмасива от по n/2 елемента се сортират рекурентно, отнема някакво време, но ние ще го вземем предвид, когато разглеждаме подзадачите.
  3. Стъпката "комбинирай" слива общо n елемента и отнема време Θ(n).
Ако помислим за двете стъпките на разделяне и комбиниране, времето за изпълнение Θ(1) за разделянето е от по-нисък порядък в сравнение с времето Θ(n) за изпълнение на стъпката на комбиниране. Затова нека мислим за времето, което двете стъпките на разделяне и комбиниране отнемат заедно, като Θ(n). За да станат нещата още по-конкретни, да кажем, че общо стъпките на разделяне и комбиниране отнемат време cn за някаква константа c.
За да оставим нещата разумно прости, да приемем, че, ако n>1, то n винаги е четно, така че, когато трябва да мислим за n/2, то винаги е цяло число. (Дори и в случая n да е нечетно, това няма да промени резултата по отношение на нотацията Θ.) Сега можем да помислим за времето за изпълнение на mergeSort на подмасив с n като сумата от два пъти времето за изпълнение на mergeSort на подмасив от (n/2) елемента (за стъпката "владей") плюс cn (за стъпките "разделяй" и "комбинирай" – в действителност само за сливането).
Сега трябва да открием времето за изпълнение на двете рекурентни извиквания за n/2 елемента. Всяко от тези две рекурентни извиквания отнема два пъти времето за изпълнение на mergeSort на подмасив от (n/4) елемента (защото трябва да разделим n/2) плюс cn/2 за сливането. Имаме две подзадачи с размер n/2 и всяка отнема време cn/2 за сливане и така общото време, което трябва за сливането на подзадачи с размер n/2, е 2⋅cn/2=cn.
Да нанесем времето за сливане в "дърво":
A diagram with a tree on the left and merging times on the right. The tree is labeled "Subproblem size" and the right is labeled "Total merging time for all subproblems of this size." The first level of the tree shows a single node n and corresponding merging time of c times n. The second level of the tree shows two nodes, each of 1/2 n, and a merging time of 2 times c times 1/2 n, the same as c times n.
Компютърните специалисти рисуват дърветата от горе надолу – обратно на начина, по който растат истинските дървета. Едно дърво е граф без цикли (пътища, които започват и завършват на едно и също място). Според конвенцията възлите на дървото се наричат върхове. Коренът е на върха. Тук коренът е отбелязан с размер на подмасива n от първоначалния масив с n елемента. Под корена има два наследяващи върха, всеки от които е отбелязан с n/2, за да покаже размерите на подмасивите за двете подзадачи с размер n/2.
Всяка от подзадачите с размер n/2 рекурентно сортира два подмасива с размер (n/2)/2 или n/4. Тъй като има две подзадачи с размер n/2, има четири подзадачи с размер n/4. Всяка от тези четири подзадачи слива общо n/4 елемента и така времето за сливане на четирите подзадачи е cn/4. Сумираме четирите подзадачи и виждаме, че общото време за сливане на всички подзадачи с размер n/4 е 4⋅cn/4=cn:
A diagram with a tree on the left and merging times on the right. The tree is labeled "Subproblem size" and the right is labeled "Total merging time for all subproblems of this size." The first level of the tree shows a single node n and corresponding merging time of c times n. The second level of the tree shows two nodes, each of 1/2 n, and a merging time of 2 times c times 1/2 n, the same as c times n. The third level of the tree shows four nodes, each of 1/4 n, and a merging time of 4 times c times 1/4 n, the same as c times n.
Какво според теб ще се случи с подзадачите с размер n/8? Ще има осем такива подзадачи, а времето за сливане на всяка ще е cn/8 за общо време за сливане 8⋅cn/8=cn:
A diagram with a tree on the left and merging times on the right. The tree is labeled "Subproblem size" and the right is labeled "Total merging time for all subproblems of this size." The first level of the tree shows a single node n and corresponding merging time of c times n. The second level of the tree shows two nodes, each of 1/2 n, and a merging time of 2 times c times 1/2 n, the same as c times n. The third level of the tree shows four nodes, each of 1/4 n, and a merging time of 4 times c times 1/4 n, the same as c times n. The fourth level of the tree shows eight nodes, each of 1/8 n, and a merging time of 8 times c times 1/8 n, the same as c times n.
Тъй като всички подзадачи стават по-малки, броят на подзадачите се удвоява на всяко "ниво" на рекурсията, но времето за сливане се разделя на две. Удвояването и разделянето се анулират и така общото време за сливане е cn за всяко ниво на рекурсията. Накрая стигаме до подзадачи с размер 1: основният случай. Трябва ни време Θ(1), за да сортираме подмасив с размер 1, защото трябва да проверим дали p<r, а тази проверка отнема време. Колко подмасива с размер 1 има? Тъй като започваме с n елемента, трябва да има n подмасива. Тъй като всеки основен случай отнема време Θ(1), да кажем, че общо основните случаи отнемат време cn:
A diagram with a tree on the left and merging times on the right. The tree is labeled "Subproblem size" and the right is labeled "Total merging time for all subproblems of this size." The first level of the tree shows a single node n and corresponding merging time of c times n. The second level of the tree shows two nodes, each of 1/2 n, and a merging time of 2 times c times 1/2 n, the same as c times n. The third level of the tree shows four nodes, each of 1/4 n, and a merging time of 4 times c times 1/4 n, the same as c times n. The fourth level of the tree shows eight nodes, each of 1/8 n, and a merging time of 8 times c times 1/8 n, the same as c times n. Underneath that level, dots are shown to indicate the tree continues like that. A final level is shown with n nodes of 1, and a merging time of n times c, the same as c times n.
Сега знаем колко време отнема сливането на подзадачите от всеки размер. Общото време за изпълнение на mergeSort е сумата на времето за сливане на всички нива. Ако в дървото има l нива, общото време за сливане е l⋅cn. А колко е l? Започваме с подзадачи с размер n и ги разделяме на половина, докато стигнем до подзадачи с размер 1. Видяхме тази характеристика, когато анализирахме двоичното търсене и отговорът е l=log2⁡n+1. Например, ако n=8, то log2⁡n+1=4 и е достатъчно сигурно, че дървото има четири нива: n=8,4,2,1. Тогава общото време за mergeSort е cn(log2⁡n+1). Когато използваме нотацията Θ, за да опишем това време за изпълнение, можем да отхвърлим членовете от нисък порядък (+1) и константния коефициент (c), което ни дава време за изпълние Θ(nlog2⁡n), както очаквахме.
Трябва да отбележим още нещо за сортирането чрез сливане. По време на сливането се прави копие на целия сортиран масив с една половина lowHalf и друга highHalf . Тъй като в някакъв момент се копират повече от константните елементи, казваме, че сортирането чрез сливане не работи на място. За разлика от него сортирането чрез пряка селекция и чрез вмъкване работят на място, тъй като никога не правят копие на повече от постоянният брой елементи на масива, в който и да било момент. Добре е да се отчита дали алгоритъмът работи на място, защото има системи, в които се предпочита работата на място, и в тогава се предпочитат такива алгоритми.
Това съдържание е резултат от съвместната дейност на преподавателите по Компютърни науки в Дартмут Thomas Cormen и Devin Balkcom, както и на екипа по компютърни науки на Кан Академия. Съдържанието е лицензирано CC-BY-NC-SA.

Искаш ли да се присъединиш към разговора?

Вписване в профила
Все още няма публикации.
Разбираш ли английски? Натисни тук, за да видиш още дискусии в английския сайт на Кан Академия.