# Първи семинар по структури от данни - 10.10.2024

## Алгоритъм
Формално понятието алгоритъм е първично. За него няма общоприета дефиниция. Все пак обаче алгоритми сме виждали и имаме някаква представа какво представляват.

За алгоритъм най - често се мисли като за крайна последователност от елементарни инструкции, използвани за да решат някакъв проблем или да извършат някакво изчисление. С течение на курса, изучавайки различните структури от данни, ще изучаваме и различните алгоритми, в които те се използват. Използването на правилните структури от данни често ни води до по - добри алгоритми. Но какво точно наричаме "по-добър алгоритъм"?

## Сложност по време
За да си отговорим на въпросът "алгоритъм А по - добър ли е от алгоритъм B", трябва да въведем някаква оценка. Първият ни опит би бил да напишем и двата алгоритъма и да ги пуснем върху достатъчно голям вход. Можем да измерим за колко време се изпълнява всеки един от тях (примерно в секунди) и да сравним двете времена.

Такъв тип оценки се правят, но те не винаги са точни. Причината за това е, че подобни оценки могат да зависят от много неща:
* Дали двата алгоритъма са пуснати на една и съща машина?
* Каква точно е машината? Какъв хардуер използва?
* Каква е операционната система на тази машина? Какви неща вървят заедно с нашите алгоритми?

И много още. Приемаме друг подход - интересуваме се как се изменя броя стъпки (елементарни инструкции), извършени от алгоритъма, с нарастване на входа. Например, ако разгледаме произволен алгоритъм, който приема като вход цяло число и прави нещо с него, дали с нарастване на входа (числото) нарастват стъпките, които алгоритъмът изпълнява? И, ако нарастват, как точно нарастват? 

## Дефиниция: Сложността е функция по големината на входа.

Нека разгледаме следния алгоритъм:
```cpp
unsigned algA(unsigned n)
{
    unsigned result = 0;
    for(unsigned i = 1; i <= n; i++)
    {
        result += i;
    }
    return result;
}
```
Този алгоритъм приема цяло число `n` и намира сумата на числата от 1 до `n`. Нараства ли броят на стъпките, които алгоритъмът изпълнява, с нарастване на входа? Отговорът е да - при вход 10 цикълът `for` ще се завърти 10 пъти. При вход 100 той ще се завърти 100 пъти.

Сега нека разгледаме друг алгоритъм, решаващ същата задача:
```cpp
unsigned algB(unsigned n)
{
    return n * (n + 1) / 2;
}
```
Формулата е добре позната (формула за аритметична прогресия). Нараства ли броят на стъпките, които алгоритъмът изпълнява, с нарастване на входа? Отговорът е не - при вход 10 и при вход 100 винаги ще имаме едно събиране, едно умножение и едно делене.

## Асимптотични нотации
Както казахме, интересува ни **как расте броя на стъпките при нарастване на входа**. В някакъв смисъл **не ни интересува колко точно са на брой а единствено как расте.** Ще въведем две нотации, които ще ни помагат да оценяваме алгоритми.

* Нотацията Θ ни дава точна граница.
* Нотацията О ни дава горна граница.

Нека използваме тези нотации за да дадем оценки на алгоритмите:

* algA = O(n)

* algA = O(n^2) - Това е вярно, понеже О е горна граница, но е безсмислено да се разглежда.

* algA = Θ(n)

* algA != Θ(n^2) - Θ е точна а не горна граница.

* algB = O(1)

* algB = O(n) - Това е вярно, понеже О е горна граница, но е безсмислено да се разглежда.

* algB = Θ(1)

* algB != Θ(n)

## Видове сложност по време
Когато разглеждаме сложността по време, имаме три случая:
* Най-добър случай
* Среден случай
* Най-лош случай

Нека се опитаме да разберем смисъла на тези понятия чрез пример:

```cpp
int linear_search(int* haysack, unsigned size, int needle)
{
    for(unsigned i = 0; i < size; i++)
    {
        if (haysack[i] == needle)
        {
            return i;
        }
    }
    return -1;
}
```
Това е алгоритъмът линейно търсене, той приема масив и число и връща индекса на числото, ако то се среща, и -1 ако не се среща в масива. В случая `n` е големината на масива (т.е. `size`). Няма смисъл да разглеждаме нарастването на търсения елемент.

* Най-добър случай: Тук приемаме оптимистичен подход. Нека елементът, който търсим, е винаги на първа позиция. Тогава, без значение колко расте масивът, винаги ще имаме едно сравнение и веднага ще връщаме от функцията. Можем да направим извод, че сложността в най - добрия случай е Θ(1).

* Най-лош случай: Най-лошият случай е когато елементът не присъства в масива. Тогава алгоритъмът прави възможно най-много стъпки. Тогава сложността е Θ(n).

* Среден случай: Анализът на средния случай е най-полезен, но и най-сложен. Можем да си мислим за него като осреднената оценка на стъпките върху всички възможни входове. Интуитивно сложността в средния случай отново е Θ(n).

Сложността в средния случай винаги се намира между сложността в най-добрия и сложността в най-лошия. Ако оценим най-лошия случай на Θ(n) а средния на Θ(n^2), то допускаме грешка.

## Сложност по памет
Сложността по памет на даден алгоритъм е броят на елементите памет, които алгоритъмът използва, без да броим паметта в която се разполага входа и паметта в която се разполага изхода. Отново използваме асимптотичните нотации за да даваме оценка.

## Пресмятане на сложности.
Нека разгледаме следния алгоритъм:
```cpp
int dummy(int n)
{
    int result = 0;
    while(n)
    {
        result++;
        n--;
    }
    return result;
}
```
Сложността на този алгоритъм е Θ(n). Защо? Отговорът "защото прави n стъпки" не е коректен. 
* Една стъпка за създаване на променливата `result` със стойност 0.

* `n` пъти увеличаваме `result` и `n` пъти намаляме `n`.

* "Една" стъпка за връщане на резултата.

Тоест тук стъпките са поне 2n + 2. И все пак алгоритъмът е със сложност Θ(n). Както казахме, **не се интересуваме от точна оценка а от това как нарастват стъпките.** Приемаме следните правила:
* Игнонираме мултипликативните константи:
    * 3n = Θ(n)
    * 7n = Θ(n)
    * 0.5n = Θ(n)
* Игнорираме събираемите
    * n + 7 = Θ(n)
    * 2n + 10 = Θ(n)
* Интересуваме се от функцията с най - висока асимптотика
    * n^2 + 7n + 3 = Θ(n^2)
    * 2^n + n^2 + 1 = Θ(2^n)

## Анализ на итеративни алгоритми
Един от начините да анализираме сложността на итеративни алгоритми е чрез метода на сумирането.
```cpp
for(int i = 0; i < n; i++)
{
    Θ(1)
}
```
$$
\sum_{i=0}^n \theta(1) = \theta(n)
$$

```cpp
for(int i = 0; i < n; i++)
{
    for(int j = 0; j < n; j++)
    {
        Θ(1)
    }
}
```
$$
\sum_{i=0}^n \sum_{j=0}^n \theta(1) = \sum_{i=0}^n \theta(n) = \theta(n^2)
$$

Забележка: Два вложени `for` цикъла не винаги означават Θ(n^2) сложност.
``` cpp
for(int i = 1; i < n; i *= 2)
{
    for (int j = 0; j < i; j++)
    {
        Θ(1)
    }
}
```

## Примери за алгоритми с различни сложности.

```cpp
bool is_odd(unsigned n)
{
    return (n % 2) == 1;
}
```

Сложност: Θ(1)

```cpp
bool is_prime(unsigned n)
{
    if(n < 2)
        return false;

    // Assuming sqrt = O(sqrt(n)).
    // (which is true in most cases)
    // https://en.wikipedia.org/wiki/Integer_square_root
    // binary search based algorithm can be used to assure Θ(lon(n)).
    unsigned square = sqrt(n);

    for(int i = 2; i <= square; i++)
    {
        if(n % i == 0)
        {
            return false;
        }
    }
    return true;
}
```
Сложност: Θ(sqrt(n))

```cpp
unsigned log_down(unsigned n, unsigned base = 2)
{
    unsigned result = 0;

    while(n)
    {
        ++result;
        n /= base;
    }
    return result;
}
```
Сложност: Θ(log(n))

Алгоритъм, който генерира всички подмножества на множество с големина n, би имал сложност Θ(2^n).

## Сортиращи алгоритми. Свойства на сортиращите алгоритми.

1. Стабилност - Запазва се относителната наредба на елементите с еднакви ключове. 
    * Не винаги сортираме числа. При сортиране на записи (примерно информация за студенти) сортираме по ключ (примерно факултетен номер).
    * Ако получим списък от записи за оценките на студенти от някой изпит, сортирани по имена, и ги сортираме със стабилен сортиращ алгоритъм по оценки, студентите с еднакви оценки ще останат сортирани и по имена.
    * Ако ги сортираме с нестабилен сортиращ алгоритъм това не е сигурно.

2. Адаптивност - Сортиращ алгоритъм нарицаме "адаптивен" ако се взема предвид текущата наредба на елементите.
3. in-place - Алгоритъм наричаме `in-place` ако не се използва допълнителна памет за неговата работа.

## Bubble sort
* Best case: Θ(n)
* Average case: Θ(n^2)
* Worst case: Θ(n^2)

* Стабилен сортиращ алгоритъм заради строгото неравенство.
* Адаптивен - Зависи от това какво разбираме под `почти сортиран` масив.
    * [1, 2, 3, 4, 5, 4] - Bubble sort би се справил добре върху този вход.
    * [2, 3, 4, 5, 1]    - В случая отново ще имаме Θ(n^2) стъпки.
* in-place: да

## Selection sort
* Best case: Θ(n^2)
* Average case: Θ(n^2)
* Worst case: Θ(n^2)

* Нестабилен сортиращ алгоритъм.
* Адаптивен - не
* in-place - да


## Insertion sort
* Best case: Θ(n)
* Average case: Θ(n^2)
* Worst case: Θ(n^2)

* Стабилен сортиращ алгоритъм.
* Адаптивен - да
* in-place - да

## Binary search
* Best case: Θ(1)
* Average case: Θ(log(n))
* Worst case: Θ(log(n))