Тема 50(9): Поняття складності алгоритму. Алгоритми впорядкування масиву.

Швидкість роботи алгоритму визначається його складністю.

Складність алгоритму – це комплексна властивість алгоритму, яка визначає:

• часову складність алгоритму – час, необхідний для виконання алгоритму, який залежіть від кількості операцій, які потрібно виконати в алгоритмі;

• ємнісна складність алгоритму – об’єм пам’яті, необхідний для розміщення вхідних даних, проміжних і кінцевих результатів, а також команд алгоритму.

Часова та ємнісна складність алгоритму тісно пов’язані між собою і кожна з них залежить від обсягу вхідних даних.

Якщо б кожна операція в комп’ютері виконувалася протягом одного й того са-мого часу t, то часову складність алгоритму Т можна було б обчислити за формулою Т = t*n, де n – кількість операцій. Але реально різні операції можуть виконуватися протягом різного проміжку часу. Тому при визначенні часової складності алгоритму інколи враховують середній час виконання однієї операції, але найчастіше – максимальний час виконання операції.

Завдання

Перегляньте відео та заповніть форму

Сортування елементів масиву методом "Сортування вибором":