Ефективність алгоритму

Важливість ефективності у плані часу виконання підкреслювала Ада Лавлейс у 1843 році з приводу механічної аналітичної машини Чарлза Беббіджа:

	Майже у всіх обчисленнях можливий великий вибір конфігурацій для успішного завершення процесу і різні угоди повинні впливати на вибір з метою виконання обчислень. Істотна річ - вибір конфігурації, яка приведе до мінімізації часу, необхідного для виконання обчислення.»
— [1]

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

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

	В усталених технічних дисциплінах поліпшення на 12% легко досяжне, ніколи не вважалося позамежним і я вірю, що так само повинно бути у програмуванні»
— [2]

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

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

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

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

Теоретичний аналіз

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

Деякі приклади нотації «O» велике :

позначення	Назва	приклади
${\displaystyle O(1)\,}$	постійне	Визначення, парне чи непарне число. Використання таблиці пошуку постійного розміру. Використання підхожої хеш-функції для вибору елемента.
${\displaystyle O(\log n)\,}$	логарифмічне	Знаходження елемента у відсортованому масиві за допомогою двійкового пошуку або збалансованого дерева, як і операції в біноміальній купі.
${\displaystyle O(n)\,}$	лінійне	Пошук елемента в несортованому списку або незбалансованому дереві (найгірший випадок). Додавання двох n-бітних чисел з використанням наскрізного переносу.
${\displaystyle O(n\log n)\,}$	квазілінійне, логарифмічно лінійне	Обчислення швидкого перетворення Фур'є, пірамідальне сортування, швидке сортування (кращий і середній випадок), сортування злиттям
${\displaystyle O(n^{2})\,}$	квадратне	Множення двох n-значних чисел за допомогою простого алгоритму, сортування бульбашкою (найгірший випадок), сортування Шелла, швидке сортування (найгірший випадок), сортування вибором, сортування вставками
${\displaystyle O(c^{n}),\;c>1}$	експоненціальне	Знаходження (точного) розв'язку задачі комівояжера за допомогою динамічного програмування. Визначення, чи є два логічних твердження еквівалентними за допомогою повного перебору

Вимірювання зазвичай виражаються як функція від розміру входу n.

Два найважливіших вимірювання:

• Час: як довго алгоритм займає процесор.
• Пам'ять: як багато робочої пам'яті (зазвичай RAM) потрібно для алгоритму. Тут є два аспекти: кількість пам'яті для коду і кількість пам'яті для даних, з якими код працює.

Для комп'ютерів, які живляться від батарей (наприклад, лептопів) або для дуже довгих/великих обчислень (наприклад, на суперкомп'ютерах), становлять інтерес вимірювання іншого роду:

• Пряме споживання енергії: енергія, необхідна для роботи комп'ютера.
• Непряме споживання енергії: енергія, необхідна для охолодження, освітлення тощо.

У деяких випадках потрібні інші, менш поширені вимірювання:

• Розмір передачі: пропускна здатність каналу може виявитися обмежувальним фактором. Для зменшення кількості переданих даних можна використовувати стиснення. Показ малюнка або зображення (як, наприклад, Google logo) може передбачати передавання десятків тисяч байт (232K в даному випадку). Порівняйте це з передачею шести байт у слові «Google».
• Зовнішня пам'ять: пам'ять, необхідна на диску або іншому пристрої зовнішньої пам'яті. Ця пам'ять може використовуватися для тимчасового зберігання або для майбутнього використання.
• Час відгуку: параметр особливо важливий для застосунків, що працюють у реальному часі, коли комп'ютер повинен швидко відповідати на зовнішні події.
• Загальна вартість володіння: параметр важливий, коли призначений для виконання одного алгоритму.

• Швидке сортування, перший відомий алгоритм зі швидкістю близько ${\displaystyle O(n\log n)}$
• Пірамідальне сортування, інший швидкий алгоритм сортування
• Двійковий пошук для пошуку в упорядкованій таблиці
• Алгоритм Бойера — Мура для пошуку рядка всередині іншого рядка

• Девід Мей, британський учений в галузі інформатики, професор інформатики Бристольського університету, засновник і головний інженер XMOS Semiconductor вважає, що одна з проблем полягає в існуванні віри, що закон Мура вирішує питання неефективності. Він запропонував «альтернативний» закон Мура (Закон Вірта)[7] :

Програми стають повільнішими більш стрімко, ніж комп'ютери стають швидшими.

Мей стверджує:

В широко розповсюджених системах зменшення вдвічі виконання команд може подвоїти життя батареї, а великі дані дають можливість для кращих алгоритмів: Зменшення числа операцій з N x N до N x log (N) має сильний ефект при великих N... Для N = 30 мільярдів, ці зміни аналогічні 50 рокам технологічних поліпшень.

• Програміст Адам Н. Розербург у своєму блозі «The failure of the Digital computer», описав поточний стан програмування як близький до «Software event horizon» (рівню програмної катастрофи, натяк на фантастичний «shoe event horizon» (рівень взуттєвої катастрофи), описаний Дугласом Адамсом в його книзі «Автостопом по галактиці»[8]). Він оцінив падіння продуктивності на 70 dB, або на «99.99999 % від можливого», в порівнянні з 1980-ми роками — «коли Артур Кларк порівняв обчислювальні здатності комп'ютерів 2001 з комп'ютером HAL у книзі „2001: Космічна Одіссея“, він вказав, що на диво малі і потужні були комп'ютери, але програми стали сумно розчаровувати».

Проводяться змагання з розробки кращих алгоритмів, критерій якості яких визначають судді:

• Wired[9]

• Аналіз алгоритмів
• Арифметичне кодування — вид ентропійного кодування зі змінною довжиною коду для ефективного стиснення даних
• Асоціативний масив — структура даних, яку можна зробити більш ефективною при застосуванні дерев PATRICIA або масивів Джуді
• Тест продуктивності — метод вимірювання порівняльного часу виконання в певних випадках
• Найкращий, найгірший і середній випадки — домовленості щодо оцінки часу виконання за трьома сценаріями
• Двійковий пошук — проста і ефективна техніка пошуку у відсортованому списку
• Таблиця галуження — техніка скорочення довжини команд, розміру машинного коду, і найчастіше, пам'яті
• Оптимізувальний компілятор — компілятор, який використовує різні методи отримання більш оптимального програмного коду при збереженні функціональних можливостей
• Обчислювальна складність математичних операцій
• Обчислювальна складність — поняття в інформатиці, що позначає залежності обсягу роботи від розміру вхідних даних
• Обчислювальна потужність комп'ютера — кількісна характеристика швидкості виконання операцій на комп'ютері
• Стиснення даних — скорочення обсягу передаваних даних і займаного дискового простору
• Індекс — дані, що збільшують швидкість вибірки даних з таблиць
• Ентропійне кодування — кодування послідовності значень з можливістю однозначного відновлення з метою зменшення обсягу даних (довжини послідовності) за допомогою усереднення ймовірностей появи елементів у закодованій послідовності
• Збирання сміття — автоматичне звільнення пам'яті після використання
• Зелені інформаційні технології — рух за впровадження «зелених» технологій, які споживають менше ресурсів
• Код Гаффмана — алгоритм ефективного кодування даних
• Improving Managed code Performance — Microsoft MSDN Library
• Локальність посилань — щоб уникнути затримок, викликаних кешуванням через доступ до нелокальної пам'яті
• Оптимізація циклів
• Керування пам'яттю
• Оптимізація (інформатика)
• Аналіз продуктивності — методи вимірювання фактичної продуктивності алгоритму в реальному часі
• Обчислення в реальному часі — приклад критичних за часом застосунків
• Одночасна багатопотоковість
• Випереджувальне виконання, коли обчислення проводяться, навіть якщо ще невідомо, чи знадобляться їх результати, або негайне обчислення як протилежність ледачих обчислень
• Часова багатопотоковість
• Шитий код — один із способів реалізації проміжної віртуальної машини при інтерпретації мов програмування (поряд з байт-кодом)
• Таблиця віртуальних методів — механізм підтримки динамічної відповідності (або методу пізнього зв'язування)

• Christopher Green (2013). Classics in the History of Psychology. Процитовано 19 травня 2013.
• Knuth D. Structured Programming with go-to Statements // Computing Surveys. — ACM, 1974. — Т. 6, вип. 4.
• Whetstone Benchmark History. Roylongbottom.org.uk. Процитовано 14 грудня 2011.
• Floating Point Benchmark: Comparing Languages (Fourmilog: None Dare Call It Reason). Fourmilab.ch. 4 серпня 2005. Процитовано 14 грудня 2011.
• Guy Lewis Steele, Jr. Debunking the 'Expensive Procedure Call' Myth, or, Procedure Call Implementations Considered Harmful, or, Lambda: The Ultimate GOTO // MIT AI Lab. AI Lab Memo AIM-443.. — 1977. — October.

• Анімація алгоритму Бойєра-Мура (Java-аплет)
• «How algorithms shape our world». Виступ Кельвіна Славіна на TED-конференції .
• Misconceptions about algorithmic efficiency in high-schools