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

Алгоритъм

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

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

Сложност по време

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

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

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

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

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

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 пъти.

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

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)

Видове сложност по време

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

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

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), то допускаме грешка.

Сложност по памет

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

Пресмятане на сложности.

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

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)

Анализ на итеративни алгоритми

Един от начините да анализираме сложността на итеративни алгоритми е чрез метода на сумирането.

for(int i = 0; i < n; i++)
{
    Θ(1)
}

$$ \sum_{i=0}^n \theta(1) = \theta(n) $$

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) сложност.

for(int i = 1; i < n; i *= 2)
{
    for (int j = 0; j < i; j++)
    {
        Θ(1)
    }
}

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

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

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

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))

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))