Вправа 1. Складність алгоритму. Завдання. Обговоріть, як дослідити ефективність використання методів мови програмування Python й алгоритмів упорядкування списків. Чи можна результати обговорення подати в термінах поняття «складність алгоритму»?
Ответы
Ответ:
Для дослідження ефективності використання методів мови програмування Python і алгоритмів упорядкування списків можна використовувати такі методи:
Емпіричне вимірювання часу виконання алгоритму на різних розмірах вхідних даних і порівняння цих часів між собою.
Математичний аналіз складності алгоритмів, який полягає в описі теоретичної швидкості росту часу виконання алгоритму в залежності від розміру вхідних даних.
Метод емпіричного вимірювання часу виконання є простим і досить точним способом визначення ефективності алгоритму. Однак він може бути не зручним для дослідження дуже великих вхідних даних або алгоритмів зі складною структурою.
Математичний аналіз складності алгоритмів дозволяє зрозуміти, як швидко збільшується час виконання алгоритму при збільшенні розміру вхідних даних. В залежності від швидкості зростання часу виконання алгоритмів можна розрізняти декілька класів складності: константна, логарифмічна, лінійна, квадратична, експоненціальна, факторіальна і т.д.
Результати обговорення можна подати в термінах поняття "складність алгоритму". Наприклад, якщо під час дослідження встановлено, що алгоритм сортування QuickSort має лінійну складність, то можна зробити висновок, що він ефективніший за алгоритм BubbleSort з квадратичною складністю.
Объяснение: