Анализ на алгоритми. Алгоритми за търсене и сортиране.

Сложност: Функция по големината на входа (N)

Пример:

• При търсене в масив - големината на входа е големината на масива
• При проверка число дали е просто - големината на входа е числото.

При анализа на алгоритми НЕ се интересуваме от точната функция! Интересуваме се само то асимптотиката на функцията. Колко бързо расте функцията при n->безкрайност.

Тук релциите за по-малко и по-равно не са тези, които познаваме. Тук визираме скоростта на растежа на функцията.

Алгоритми за търсене.

• Linear search
• Binary search

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

• Bubble sort
• Selection sort

Задачи

Задача 1: