1. Оценка на ефективността на алгоритмите. Нотация голямо О. Техника за извличане на оценка Big-O на примера на алгоритъм за сортиране чрез вмъкване. Класификация на алгоритмите по сложност.
Анализът на алгоритмите е ключът към разбирането им в степен, достатъчна за ефективността на приложението им при решаване на практически задачи. Има два основни начина за анализ - провеждане на изчерпателни експерименти или предварителен математически анализ на програмата.
Оценка на ефективността на алгоритмите– трудоемкост (време за изпълнение на програмата) и необходимо количество памет. Аналитично оценките се получават въз основа на изчисляването на основните операции на сравнение и обмен. По правило тези операции са концентрирани във вътрешните цикли на алгоритъма.
Основнатахарактеристика на алгоритъма за сортиране е индексът на изчислителната сложност, който зависи от броя на сортираните елементи.
Вториятпоказател за ефективността на алгоритъма за сортиране е количеството допълнителна памет, използвана за сортиране. По този показател алгоритмите се разделят на три групи:
- алгоритми, които организират сортиране на едно и също място и не използват допълнителна памет (с изключение на стека и таблицата);
- алгоритми, които използват представяне на свързан списък или други указателни или индексни структури;
- алгоритми, които изискват допълнителна памет за настаняване на друго копие на сортирания масив.
Нотация с голямо О- ред на растеж или асимптотична оценка на растежа. Big-O = O(n): O е количеството данни, n е нотацията.
Времето, необходимо за сортиране на масив, зависи от размера на сортирания масив и неговия ред. Времето за работа на алгоритъма се определя от броя на стъпките, които предприема. Ще приемем, че терминът на псевдокода изисква не повече от фиксиран брой елементарни операции, ако низът не е формулировка на сложни действия. В последния случай линията отговаря на програмна функция, но в основнияалгоритъм, то съответства на извикване на тази функция. Извикването на функция и нейното изпълнение се различават по време.
Когато анализираме, до всеки ред ще маркираме неговата цена - броя на елементарните операции C i и броя на изпълнението на този ред. Нека изведем основния параметър, използван при анализа - размерността на масива n , т.е. брой елементи.