Презентація "ПОНЯТТЯ АЛГОРИТМУ. ВИЗНАЧЕННЯ ЙОГО СКЛАДНОСТІ"

ПОНЯТТЯ АЛГОРИТМУ. ВИЗНАЧЕННЯ ЙОГО СКЛАДНОСТІБодю К. О. ліцей №120 ДМР

Алгоритм — це чітко визначена послідовність дій або інструкцій, які виконуються для вирішення певної задачі або досягнення конкретного результату. Простіше кажучи, алгоритм — це рецепт, який вказує, які кроки потрібно виконати і в якому порядку, щоб отримати бажаний результат. ЩО ТАКЕ АЛГОРИТМ?

Існує три основні види алгоритмів: Лінійні алгоритми: виконання команд відбувається послідовно одна за одною без відхилень. Алгоритми з розгалуженням: виконання залежить від умов, що визначають один з декількох можливих шляхів, по якому піде алгоритм. Циклічні алгоритми: містять повторення однієї або кількох дій. ВИДИ АЛГОРИТМІВ

ПРИКЛАДИ АЛГОРИТМІВЛінійний алгоритм. Алгоритм з розгалуженням. Циклічний алгоритм

СКЛАДНІСТЬ АЛГОРИТМІВСкладність алгоритму - характеристика, що показує кількість ресурсів, які споживає алгоритм під час виконання. Можна виділити такі складові складності алгоритму: Логічна Статична Часова Ємнісна

ВИДИ СКЛАДНОСТІ АЛГОРИТМІВЧасова складність - вимірює час, необхідний для виконання алгоритму. Вимірюється у кількості команд, або у кількості повторень циклів в алгоритміПросторова складність - вимірює обсяг пам’яті, необхідний для виконання алгоритму. Дана складність важлива при оптимізації програм

ЩО ВПЛИВАЄ НА СКЛАДНІСТЬ АЛГОРИТМІВ?Є одним з найважливіших факторів, адже чим більший розмір даних, тим більше часу та пам’яті необхідно для їх обробки. Розмір вхідних даних. Алгоритми, що використовують менше пам’яті зазвичай працюють швидше та ефективніше. Ефективність використання пам’ятіЗалежно від того, які операції і над якими структурами даних виконуються - може бути використана різна кількість ресурсів. Наприклад, відсортувати масив даних або знайти в ньому елемент - займає різну кількість часу. Типи операцій

Що таке О(n)? У даному записі n - кількість вхідних даних. О - скорочення від терміну “О-нотація”. Отже О(n) - це функція, яка показує, як буде змінюватися складність алгоритму при зміні кількості вхідних даних. О - НОТАЦІЯ

O(1)Стала складність. Час роботи алгоритму не залежить від кількості вхідних даних. Визначення значення першого елемента масиву. O(n)Лінійна складність. Подвоєння кількості задач подвоїть і необхідний час. Вивести на екран всі елементи масиву через цикл. 5 елементів - 5 повторень циклу, 10 елементів - 10 повторень. O(n²)Квадратична складність. Подвоєння кількості задачі в чотири рази збільшує необхідний час. Час роботи алгоритму зростає пропорційно квадрату кількості оброблюваних елементів. Алгоритм сортування бульбашкою, містить два цикли для обробки масиву. Також інші алгоритми сортування. O(n³)Кубічна складність. Подвоєння кількості задачі у вісім разів збільшує необхідний час. Множення матриць. ПОШИРЕНІ СКЛАДНОСТІ АЛГОРИТМІВ

ДЯКУЮ ЗА УВАГУ