# Втори семинар по структури от данни - 17.10.2024

## Анализ на рекурсивни алгоритми.
В първи семинар разгледахме метод за анализиране на итеративни алгоритми. Този метод не работи когато анализираме рекурсивни алгоритми. За да намерим сложността на рекурсивен алгоритъм използваме рекурентни уравнения.

### Рекурентно уравнение
* Рекурентно уравнение е уравнение, което изразява общия член на някаква редица от числа чрез предишните членове.

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

Нека разгледаме следния пример:
```cpp
void sum_rec(int* arr, unsigned size, int& sum)
{
    if(size == 0)
        return;
    
    sum += arr[0];
    
    return sum_rec(arr + 1, size - 1, sum);
}
```

Какво би било рекурентното уравнение, което описва този рекурсивен алгоритъм? Нека с променливата `n` означаваме големината на масива.

* Разглеждаме дъното. При n = 0 имаме Θ(1) работа.
* В противен случай, имаме едно добавяне и извикване на алгоритъма с вход `n - 1`.

Съставяме уравнението:
* T(0) = 1
* T(n) = T(n - 1) + 1

Решение на рекурентно уравнение наричаме затворена формула. Решение на горния пример би било:

T(n) = n + 1

## Методи за решаване на рекурентни уравнения

### 1. Чрез развиване
Винаги можем да започнем да развиваме рекурентното уравнение търсейки някаква закономерност.

$$
T(n) = T(n - 1) + \theta(1) = T(n - 2) + \theta(1) + \theta(1) = \newline
T(0) + \theta(1) + \dots + \theta(1) = \newline
(n + 1) * \theta(1) = \theta(n)
$$

### Чрез дърво на рекурсията
Всеки рекурсивен алгоритъм образува дърво на рекурсията. Разглеждайки броя върхове и работата, която се "извършва" във всеки връх, височината на дървото и т.н. можем да направим изводи за решението на рекурентната редица. 

Нека разгледаме следното рекурентно уравнение:
* T(0) = 1
* T(1) = 1
* T(n) = 2 * T(n / 2) + n

Това рекурентно уравнение описва работата на алгоритъмът `Merge Sort`, който ще разгледаме съвсем скоро. Как изглежда дървото на рекурсията?

![tree-merge](media/rec_tree.png)

Височината на това дърво е приблизително log(n). При стойност на параметъра `k = log_2(n)` стойността в листото е 1.
На всяко ниво имаме Θ(n) работа. Трябва да забележим, че работата за ниво j се смята по следната формула:

$$
2^j * \frac{\theta(n)}{2^j} = \theta(n)
$$ 

Това ще рече броят на върховете на всяко ниво умножен по работата, която се извършва във върха на дървото.

Щом броя на нивата е Θ(log(n)) а на всяко ниво се извършва Θ(n) работа, то търсената сложност е Θ(n log(n)).

### Други методи

## Примери
Нека разгледаме някои примери за рекурентни уравнения.

$$
T(0) = \theta(1)
\newline
T(n) = 3T(n - 1) + \theta(1)
$$

Дървото на рекурсията би изглеждало по следния начин:
![tree-recur](media/recurr2.png)

Нивата на това дърво ще са n на брой. Всеки елемент е с единица по - малък от баща си. Също така, на всяко ниво има 3^j върха, където j е номерът на нивото (номерираме от 0). Всеки възел извършва Θ(1) работа. Сумираме по нива:

$$
\sum_{i = 0}^n 3^i * \theta(1) = \frac{3^{n + 1} - 1}{2} * \theta(1) = \theta(3^n)
$$

## Алгоритмична схема "разделяй и владей"
* Разделяй - Ако входът е достатъчно голям той се разделя на части и се преминава към стъпката **владей**. В противен случай (ако входът е достатъчно малък) задачата се решава по някакъв тривиален начин. (пример е дъното на рекурсията в `Merge Sort` където масив с големина 0 или 1 е тривиално сортиран.)
* Владей   - Пускаме алгоритъма върху всяка от частите и получаваме резултатите.
* Комбинирай - Използваме тези резултати за да получим желания от нас резултат.

## Алгоритъмът Merge Sort
Първо, нека се запознаем с функцията `merge`. Тя приема два сортирани масива и като резултат създава сортиран масив. Важно условие е масивите да са сортирани. Ако това не е така функцията не прави нищо логично.

Ако имаме масив с n елемента и успешно сортираме лявата и дясната половина, то извиквайки функцията `merge` ще получим желания сортиран масив. Но как да сортираме лявата и дясната половина?

Спомняме си, че пишем сортиращ алгоритъм. Извиквам mergeSort рекурсивно върху лявата и дясната половина на масива и след като ги сортира викаме функцията merge. mergeSort ще продължи да разбива масива на две, после левия и десния подмасив на още две и т.н.  

Масив от един елемент е сортиран и ще използваме този случай като дъно на рекурсията.

Нека разгледаме следната диаграма:
![merge](media/merge.png)

Оцветените в зелено клетки са подмасивите, на които вече е бил извикан merge.

Следната диаграма представя визуално как работи функцията `merge`:
![merge-func](media/merge-func.png)

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

Сложността на `Merge Sort` се описва чрез рекурентната редица, използвана като пример за решение използващо метода с дърво на рекурсията. И в трита случая имаме Θ(n log(n))

Стабилен - Да

Адаптивен - Не

in-place - Не

Сложност по памет - Θ(n)

## Алгоритъмът Quicksort
Нека предположим, че избираме произволен елемент от `p` от `n` елементи, които искаме да сортираме. `Quicksort` разделя останалите `n - 1` елемента на две групи - тези, които са по - малки от `p` и тези, които са по - големи. Всеки от по - малките елементи се намира вляво от всеки от по - големите.

Подобно разделяне ни носи две неща:

* Избраният елемент `p` остава на точната позиция на която ще бъде в сортирания масив.
* След това разбиване никой елемент не се премества от лявата част в дясната. Това означава, че можем да разглеждаме двете части като отделни масиви!

Функцията, която използваме за да направи такова разделение, наричаме `partition`. След като изберем елемент (наричан `pivot`) извикваме `partition` върху масива и след като тя приключи рекурсивно извикваме `Quicksort` върху лявата подмасива на по - малките елементи и този на по - големите.

* Worst case complextiy = O(n^2) - Можем винаги да избираме най - големия или най - малкия. Тогава няма да имаме два подмасива а един с големина `n - 1`.
* Average case = O(nlog(n)) - Добре е тук да обърнем внимание на средния случай като той ни дава много по - добра представа за реалния потенциал на `Quicksort`. Въпрки, че в най - лошия случай това е квадратичен алгоритъм, очакваме че няма да вземем най - големия, нито най - малкия, а елемент близък до средния по големина.
* Стабилен - не, `partition` не гарантира, че ще запази първоначалната наредба на елементите.
* in place - да

## std::partition, std::merge