Аналіз алгоритмів

Для пошуку запису можуть використовуватися алгоритми як бінарного, так і лінійного пошуку. В даному прикладі, пошук рядка «Motin, Athur» у списку довжиною 33 елементи для бінарного пошуку виконується за 5 кроків (позначено ціановим кольором), і за 28 кроків для лінійного (маджентовий колір).

Графіки функцій, що часто використовуються в алгоритмічному аналізі, визначають кількість операцій N в залежності від розміру вхідних даних n.

Аналіз алгоритмів — це процес визначення обчислювальної складності алгоритмів, тобто кількості часу, пам'яті чи інших ресурсів, необхідних для виконання алгоритмів. Як правило, це передбачає визначення функції, яка пов'язує розмір вхідних даних алгоритму з кількістю кроків виконання (його часовою складністю) або кількістю місця, що він використовує (його просторовою складністю). Алгоритм вважається ефективним, якщо значення цієї функції малі або зростають повільно у порівнянні зі збільшенням розміру вхідних даних. Різні входи однакової довжини можуть призводити до різної поведінки алгоритму, тому найкращі, найгірші та середні описи цих випадків можуть мати практичний інтерес. Якщо не вказано інше, функція, що описує складність алгоритму, зазвичай є верхньою межею, тобто, визначає його складність для найгірших випадків вхідних даних.

Термін «аналіз алгоритмів» був введений Дональдом Кнутом. Аналіз алгоритмів є важливою частиною більш загальної теорії обчислювальної складності, яка встановлює теоретичні оцінки ресурсів, необхідних будь-якому алгоритму, що вирішує задану обчислювальну задачу. Ці оцінки надають дослідникам розумні припущення щодо напрямків пошуку ефективних алгоритмів.

У теоретичному аналізі алгоритмів їх часто оцінюють в асимптотично, тобто, оцінкою функції складності для довільно великих вхідних даних. Для цього використовуються нотації «О» великого, великих Омега і Тета. Наприклад, бінарний пошук виконується за кількість кроків, пропорційну логарифму довжини відсортованого списку, в якому ведеться пошук, або за O(log(n)), відоме як «логарифмічний час». Звичайно асимптотичні оцінки використовуються тому, що різні рішення однієї і тієї ж задачі можуть мати різну ефективність. Звичною є ситуація коли ефективність двох «розумних» реалізацій одного алгоритму можуть відрізнятися сталим множником, який називається прихованою сталою.

Точні (не асимптотичні) вимірювання ефективності можуть бути обчислені, але потребують деяких припущень стосовно реалізації алгоритму, відомі як модель обчислення. Модель обчислення може бути визначена в термінах абстрактного комп'ютера, такого як машина Тюрінга, також в ній визначається час виконання кожної операції або робиться припущення, що всі операції виконуються за однаковий час. Наприклад, якщо відсортований список, до якого застосовується бінарний пошук, має n елементів, а також вважаємо, що кожна операція зчитування елемента списку виконується за якусь сталу одиницю часу, тоді, для отримання результату потрібно максимум log₂ n + 1 одиниць часу.

Вагові моделі

Оцінки ефективності часу залежать від того, що ми визначаємо як крок алгоритму. Щоб аналіз відповідав дійсному часу виконання, час, необхідний для виконання кроку, повинен гарантовано бути обмеженим константою. Тут слід бути обережним; наприклад, деякі моделі аналізу підраховують суму двох чисел як один крок. В деяких випадках це припущення може сильно вплинути на результат аналізу. Наприклад, якщо числа, що беруть участь у обчисленні, можуть бути довільно великими, тоді час, необхідний для операції додавання, вже не можна вважати сталим.

В основному використовуються наступні дві моделі визначення вартості операції:

• модель рівномірної ваги, приписує константну вагу (час) для кожної машинної операції незалежно від розміру даних, які оброблюються кожною з цих операцій
• логарифмічна модель, приписує вагу для операції пропорційну кількості біт в їх операндах

Остання модель є більш обтяжливою у використанні, тому її використовують тільки тоді, коли це дійсно необхідно, наприклад, при аналізі арифметичних алгоритмів з довільною точністю, в тому числі тих, що використовуються в криптографії.

Ключовим моментом, який часто пропускається, є те, що загально відомі оцінки алгоритмічної складності задач часто призначені для більш обмеженої моделі обчислення, ніж набір операцій, які можна використовувати на практиці, тому в реальності існують швидші версії алгоритмів.

Аналіз часу виконання

Аналіз часу виконання є теоретичною класифікацією, що оцінює, а тому і передбачає, збільшення часу виконання алгоритму при збільшенні розміру його вхідних параметрів (зазвичай позначається як n). Ефективність виконання є цікавою з точки зору комп'ютерних наук: програма може виконуватись секунди, години або навіть роки, залежно від того, який алгоритм вона реалізує. Попри те, що методики профілювання програмного забезпечення використовуються для вимірювання часу виконання алгоритму на практиці, вони не можуть забезпечити дані часу для всієї безлічі можливих входів; останнє може бути досягнуто лише теоретичними методами аналізу.

Недоліки емпіричних метрик

Оскільки алгоритми є незалежними від платформи (тобто даний алгоритм може бути реалізований довільною мовою програмування на довільному комп'ютері, на якому працює довільна операційна система), існують додаткові істотні недоліки використання емпіричного підходу для порівняльної оцінки продуктивності даного набору алгоритмів.

Візьмемо як приклад програму, яка шукає певний запис у відсортованому списку розміру n. Припустимо, що ця програма була реалізована на комп'ютері A, найсучаснішій машині, використовуючи лінійний алгоритм пошуку, і на комп'ютері B, набагато повільнішій машині, використовуючи алгоритм бінарного пошуку. Тестування продуктивності відповідних програм на цих двох комп'ютерах може виглядати приблизно так:

n (довжина списку)	Час виконання на комп'ютері A (в наносекундах)	Час виконання на комп'ютері В (в наносекундах)
16	8	100 000
63	32	150 000
250	125	200 000
1 000	500	250 000

Виходячи з цих показників, було б легко дійти до висновку, що комп'ютер A виконує алгоритм, який набагато кращий за ефективністю від комп'ютера B. Однак, якщо розмір вхідного списку збільшити до достатньої кількості, становиться очевидним те, що це твердження помилкове:

n (довжина списку)	Час виконання на комп'ютері A (в наносекундах)	Час виконання на комп'ютері В (в наносекундах)
16	8	100 000
63	32	150 000
250	125	200 000
1 000	500	250 000
…	…	…
1,000,000	500,000	500,000
4,000,000	2,000,000	550,000
16,000,000	8,000,000	600,000
…	…	…
63,072 × 1012	31,536 × 1012 наносекунд, або 1 рік	1,375,000 наносекунд, або 1.375 мілісекунд

Комп'ютер A, який виконує програму лінійного пошуку, має лінійну швидкість росту: це значить, що час виконання програми прямо пропорційний його вхідному розміру. Подвоєння вхідного розміру подвоює час виконання, чотирикратний вхідний розмір вчетверо збільшує час виконання і так далі. З іншого боку, комп'ютер B, який виконує програму бінарного пошуку, має логарифмічну швидкість росту. Чотирикратне збільшення вхідного розміру збільшує час виконання на постійну величину (в даному прикладі на 50000 нс). Попри те, що комп'ютер A нібито є швидшим, комп'ютер B неминуче перевершить комп'ютер А у часі виконання надалі, оскільки він виконує алгоритм з набагато меншою швидкістю зростання.

Порядки росту

Неформально можна сказати, що алгоритм демонструє швидкість росту порядку математичної функції, якщо за певним вхідним розміром n, функція $f(n)$ помножена на позитивну константу забезпечує верхню межу або границю часу виконання цього алгоритму. Іншими словами, для заданого вхідного розміру n, що більше ніж деяка n₀, і константи c, час роботи цього алгоритму ніколи не буде більше ніж $c\times f(n)$. Ця концепція часто виражається за допомогою позначення «О» великого. Наприклад, при виконанні сортування включенням, коли розмір вхідних даних збільшується, час виконання зростає квадратично, сортування включенням можна віднести до порядку $O(n^{2})$.

Нотація «О» великого — це зручний спосіб виразити найгірший варіант даного алгоритму, хоча вона також може бути використана для вираження помірного випадку: наприклад, найгіршим сценарієм для швидкого сортування є $O(n^{2})$, але час виконання в середньому дорівнює $O(n\log {n})$.

Актуальність

Аналіз алгоритмів є важливим на практиці, оскільки випадкове або ненавмисне використання неефективного алгоритму може суттєво вплинути на продуктивність системи. У чутливих до часу додатках, алгоритм, який займає занадто багато часу, може зробити його результати застарілими або непотрібними. Неефективними алгоритми можуть полягати у неекономному використанні обсягу обчислювальної потужності або пам'яті, що може робити його непотрібним в практичному сенсі.

Найбільш вибагливими у цьому сенсі є системи реального часу: алгоритми, що використовуються в них, повинні бути детермінованими, економними до ресурсів та швидкими, бо від них часто залежать людські життя або критична інфраструктура. Наприклад, автопілот літака чи автоматизована система керування ядерного реактора на АЕС.

Константні множники

Аналіз алгоритмів, як правило, зосереджується на асимптотичній продуктивності, особливо на елементарному рівні, але в реальних програмах постійні множники є дуже важливими, бо дані реального світу завжди обмежені за розмірами. Обмежені, як правило, розміром адресної пам'яті, тому на 32-бітних машинах це 2³² = 4 ГБ (більше, якщо використовується сегментована пам'ять), і 2⁶⁴ = 16 EiB на 64-бітних машинах. Таким чином, з огляду на обмежений розмір, порядок росту (часу або простору) може бути замінений на постійний коефіцієнт, і в цьому сенсі всі реальні алгоритми є $O(1)$ для достатньо великої константи або для досить малих даних.

Така інтерпретація в першу чергу корисна для функцій, які ростуть надзвичайно повільно: двійковий повторний логарифм ($\log _{2}^{*}$) менше ніж 5 для всіх практичних даних (2⁶⁵⁵³⁶ біт); двійковий логарифм логарифма ($\log _{2}{\log _{2}{n}}$) менше ніж 6 для практично всіх даних (2⁶⁴ біт); і двійковий логарифм ($\log _{2}{n}$) менше ніж 64 для практично всіх реальних даних (2⁶⁴ біт). Алгоритм з нестійкою складністю може, тим не менш, бути більш ефективним на реальних даних, ніж алгоритм з постійною складністю, якщо накладні витрати на алгоритм постійного часу дають більший постійний коефіцієнт: наприклад, один з них може мати $K>k\log {\log {n}}$ поки $K/k>6$ та $n<2^{2^{6}}=2^{64}$.

Для великих даних лінійні або квадратичні множники не можуть бути проігноровані, але для малих даних асимптотично неефективний алгоритм може бути більш ефективним. Цей факт застосовується в гібридних алгоритмах, таких як Timsort, які використовують асимптотично ефективний алгоритм (у випадку Timsort — сортування злиттям, з часовою складністю $n\log {n}$), але перемикаються на асимптотично неефективний (сортування включенням, з часовою складністю $n^{2}$) для малих даних, бо простіший алгоритм швидше на малих даних.

Див. також

• Аналіз паралельних алгоритмів
• Амортизаційний аналіз
• Часова складність алгоритму
• Чисельні методи
• NP-повна задача
• Майстер-метод
• Теорія складності обчислень
• Оптимізація
• Профілювання
• Масштабовність
• Чисельні методи оптимізації