Поняття складності алгоритмів

Чашук О. Ф., вчитель інформатики ЗОШ№23, Луцьк

Чашук О. Ф., вчитель інформатики ЗОШ№23, Луцьк

Чашук О. Ф., вчитель інформатики ЗОШ№23, Луцьк. Як можна опрацьовувати табличні величини. Як опрацьовувати дані в деякому наборіЩо розуміють під поняттям «складність алгоритму»

Чашук О. Ф., вчитель інформатики ЗОШ№23, Луцьк. Поняття складності алгоритмів

Чашук О. Ф., вчитель інформатики ЗОШ№23, Луцьк. Поняття «складність алгоритму»Який час потрібний для виконання програми, що реалізує певний алгоритм? Чи можна взагалі отримати результати обчислення за даним алгоритмом на комп’ютері?Питання: Теорія алгоритмів — розділ інформатики, що займається дослідженням складності алгоритмів для розв’язування задач на основі формально визначених моделей обчислювальних пристроїв.

Чашук О. Ф., вчитель інформатики ЗОШ№23, Луцьк. Поняття «складність алгоритму»Складність алгоритму. Складність алгоритму — це кількісна характеристика, що відображує споживані алгоритмом ресурси під час свого виконання. Логічна складність— кількість людино-місяців, витрачених на створення алгоритму. Статична складність — довжина опису алгоритмів (кількість операторів). Часова складність— час виконання алгоритму.Ємнісна складність— кількість умовних одиниць пам’яті, необхідних для роботи алгоритму.

Чашук О. Ф., вчитель інформатики ЗОШ№23, Луцьк. Поняття «складність алгоритму»Часова складність алгоритму — характеристика продуктивності алгоритму, що визначається кількістю елементарних операцій, які потрібно виконати для реалізації алгоритму. Лінійна складність O (n): подвоєння розміру задачі подвоїть і необхідний час; приклади — алгоритм пошуку найбільшого елемента в невідсортованому списку, для чого потрібно переглянути всі n елементів списку; алгоритм додавання/віднімання чисел з n цифр. Квадратична складність O (n2): час роботи алгоритму зростає пропорційно квадрату кількості оброблюваних елементів, подвоєння розміру задачі вчетверо збільшує необхідний час; приклад — алгоритм сортування, що виконує два вкладені цикли перебору списку. Кубічна складність O (n3): подвоєння розміру задачі збільшує необхідний час у вісім разів. Припустімо, що певним алгоритмом потрібно виконати 4n3+7n умовних операцій, щоб опрацювати n елементів вхідних даних. При збільшенні n на час роботи буде значно більше впливати піднесення n до кубу, ніж множення його на 4 або ж додавання 7n.

Розгадай. Анаграму. Чашук О. Ф., вчитель інформатики ЗОШ№23, Луцьк

Чашук О. Ф., вчитель інформатики ЗОШ№23, Луцьк. Розгадай СКЛАДНІСТЬСТАКЛНІДСЬ

Чашук О. Ф., вчитель інформатики ЗОШ№23, Луцьк. Домашнє завдання. Вивчити §14 стор. 162-165 Опрацювати всі запитання і завдання з рубрик. Заповнити словничок Теорія алгоритмів, складність алгоритму, логічна складність, статична складність, часова складність, ємнісна складність, лінійна складність, квадратична складність, кубічна складність

Чашук О. Ф., вчитель інформатики ЗОШ№23, Луцьк. Працюємо за комп'ютером. Завдання . Таймер. Приклад програми

Чашук О. Ф., вчитель інформатики ЗОШ№23, Луцьк. Працюємо за комп'ютером. Завдання 1. Пошук найменшого. Завдання. Порівняйте час виконання програм.

Чашук О. Ф., вчитель інформатики ЗОШ№23, Луцьк. Працюємо за комп'ютером. Завдання 2. Упорядкування. Завдання. Порівняйте час виконання програм.

Чашук О. Ф., вчитель інформатики ЗОШ№23, Луцьк. Працюємо за комп’ютером