й зовнішній цикл по точності включає в себе кількісно-залежний фрагмент по розмірності.
. Порядкової-залежні по трудомісткості алгоритми. Серед розмаїття параметрично-залежних алгоритмів виділимо ще оду групу, для якої кількість операцій залежить від порядку розташування вихідних об'єктів. Нехай безліч D складається з елементів (d1, ..., dn), і | | D | | = N,
Визначимо Dp = {(d1, ..., dn)}-безліч всіх упорядкованих N-ок з d1, ..., dn, відзначимо, що | Dp | = n!. Якщо Fa (iDp) В№ Fa (jDp), де iDp, jDp ГЋ Dp, то алгоритм будемо називати порядкової-залежним по трудомісткості.
Прикладами таких алгоритмів можуть служити ряд алгоритмів сортування, алгоритми пошуку мінімуму і максимуму в масиві.
2. Тимчасова та емкостная складність алгоритмів
У даному розділі розглянемо дві характеристики складності алгоритмів - тимчасова і емкостная. Одиниці виміру складності будемо прив'язувати до класу архітектур найбільш поширених ЕОМ. Тимчасову складність будемо підраховувати у виконуваних командах: кількість арифметичних операцій, кількість порівнянь, пересилань (залежно від алгоритму). Ємкісна складність буде визначатися кількістю скалярних змінних, елементів масивів, елементів записів або просто кількістю байт. p align="justify"> Одна з властивостей алгоритму - масовість. У загальному випадку кількість операцій і необхідна пам'ять залежать від вихідних даних, тобто є функціями вектора X = (х1, х2, ..., хn) вихідних даних. З точки зору математичного аналізу складності, порівняння алгоритмів, їх класифікації хотілося б, щоб функції складності (x1, x2, ..., xn) виражалися у вигляді формул з використанням звичайних, елементарних математичних функцій. Тоді виявився б доступнимбогатий арсенал засобів класичної математики. Але це не завжди можливо, так як вихідні дані можуть бути нечисловими (графи, географічні карти, рядки символів, звуки і т. д.). Тому складність алгоритму a розглядається як функція від деякого інтегрованого числового параметра V, що характеризує вихідні дані. Позначимо: T a (V) - тимчасова складність алгоритму a ; S a (V) - емкостная складність. Параметр V, що характеризує дані, називають іноді об'ємом даних або складністю даних. Обидва ці терміни не зовсім точні. Вибір параметра V залежить не тільки від виду даних, але і від виду алгоритму або від завдання, яку цей алгоритм вирішує. Розглянемо два приклади.
Відшукання функцій складності алгоритмів важливо як з...
