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

'''Ефективність алгоритму'''&nbsp;— це властивість [[Алгоритм|алгоритму]], пов'язана з [[Обчислювальні ресурси|обчислювальними ресурсами]], використовуваними алгоритмом. Алгоритм повинен бути [[Теорія алгоритмів|проаналізований]] з метою визначення необхідних йому ресурсів. Ефективність алгоритму можна розглядати як аналог виробничої продуктивності повторюваних або безперервних процесів.

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

: ''Зауважимо, що дана стаття '''НЕ''' про оптимізацію алгоритму, яка обговорюється в статтях [[Оптимізація (інформатика)|оптимізація програми]], [[оптимізувальний компілятор]], [[оптимізація циклів]], {{Нп|оптимізатор об'єктного коду||en|Object code optimizer}} тощо. Термін «оптимізація» сам по собі вводить в оману, оскільки все, що може бути зроблено, потрапляє під визначення «покращення».''

== Історія питання ==
Важливість ефективності у плані часу виконання підкреслювала [[Ада Лавлейс]] у 1843 році з приводу механічної аналітичної машини [[Чарлз Беббідж|Чарлза Беббіджа]]:
{{цитата|Майже у всіх обчисленнях можливий великий вибір конфігурацій для успішного завершення процесу і різні угоди повинні впливати на вибір з метою виконання обчислень. Істотна річ - вибір конфігурації, яка приведе до мінімізації часу, необхідного для виконання обчислення.»||{{Sfn|Green, 2013}}}}
Ранні електронні комп'ютери були дуже обмежені як за швидкістю, так і за пам'яттю. У деяких випадках було усвідомлено, що існує [[Просторово-часова домовленість|компроміс часу і пам'яті]], за якого задача повинна або використовувати велику кількість пам'яті для досягнення високої швидкості, або застосовувати більш повільний алгоритм, який використовує невелику кількість робочої пам'яті. В цьому випадку використовувався найбільш швидкий алгоритм, для якого вистачало наявної пам'яті.

Сучасні комп'ютери набагато швидші від тих ранніх комп'ютерів і мають значно більше пам'яті (гігабайти замість кілобайт). Проте, [[Дональд Кнут]] підкреслює, що ефективність залишається важливим фактором:
{{цитата|В усталених технічних дисциплінах поліпшення на 12% легко досяжне, ніколи не вважалося позамежним і я вірю, що так само повинно бути у програмуванні»||{{Sfn|Knuth|1974}}}}

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

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

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

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

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

Деякі приклади нотації [[Нотація Ландау|«O» велике]] :
{| class="wikitable"
! позначення
! Назва
! приклади
|-
| <math>O(1)\,</math>
| [[Часова складність алгоритму|постійне]]
| Визначення, парне чи непарне число. Використання [[Таблиця пошуку|таблиці пошуку]] постійного розміру. Використання підхожої [[Хеш-функція|хеш-функції]] для вибору елемента.
|-
| <math>O(\log n)\,</math>
| [[Часова складність алгоритму|логарифмічне]]
| Знаходження елемента у відсортованому масиві за допомогою [[Двійковий пошук|двійкового пошуку]] або збалансованого [[Дерево (структура даних)|дерева]], як і операції в [[Біноміальна купа|біноміальній купі]].
|-
| <math>O(n)\,</math>
| [[Часова складність алгоритму|лінійне]]
| Пошук елемента в несортованому списку або незбалансованому дереві (найгірший випадок). Додавання двох ''n''-бітних чисел з використанням [[Суматор|наскрізного переносу]].
|-
| <math>O(n\log n)\,</math>
| [[Часова складність алгоритму|квазілінійне]], логарифмічно лінійне
| Обчислення [[Швидке перетворення Фур'є|швидкого перетворення Фур'є]], [[пірамідальне сортування]], [[швидке сортування]] (кращий і середній випадок), [[сортування злиттям]]
|-
| <math>O(n^2)\,</math>
| [[Часова складність алгоритму|квадратне]]
| Множення двох ''n''-значних чисел за допомогою простого алгоритму, [[сортування бульбашкою]] (найгірший випадок), [[сортування Шелла]], швидке сортування (найгірший випадок), [[сортування вибором]], [[Сортування включенням|сортування вставками]]
|-
| <math>O(c^n),\;c>1</math>
| [[Часова складність алгоритму|експоненціальне]]
| Знаходження (точного) розв'язку [[Задача комівояжера|задачі комівояжера]] за допомогою [[Динамічне програмування|динамічного програмування]]. Визначення, чи є два логічних твердження еквівалентними за допомогою [[Пошук грубою силою|повного перебору]]
|}

=== Перевірні випробування: вимірювання продуктивності ===
Для нових версій програмного забезпечення або для забезпечення порівняння з конкурентними системами іноді використовуються [[Тест продуктивності|тести]], що дозволяють порівняти відносну продуктивність алгоритмів. Якщо, наприклад, випускається новий алгоритм [[Алгоритм сортування|сортування]], його можна порівняти з попередниками, щоб переконатися, що алгоритм щонайменше настільки ж ефективний на відомих даних, як і інші. Тести продуктивності можуть бути використані користувачами для порівняння продуктів від різних виробників для оцінки, який продукт буде більше підходити під їхні вимоги в термінах функціональності і продуктивності.

Деякі тести продуктивності дають можливість проведення порівняльного аналізу різних [[Компільована мова програмування|компільованих]] і [[Інтерпретована мова програмування|інтерпретованих мов]], як, наприклад, Roy Longbottom's PC Benchmark Collection{{Sfn|Benchmark History}}, а {{Нп|The Computer Language Benchmarks Game||en|}} порівнює продуктивність реалізацій типових задач в деяких мовах програмування.

Досить легко створити [[Зроби це сам|«саморобні»]] тести продуктивності для отримання уявлення про відносну ефективність різних мов програмування, використовуючи набір користувацьких критеріїв, як це зробив Хрістофер Коувел-Шаг у статті «Nine language Performance roundup»).<ref>{{Cite web |url=http://www.osnews.com/story/5602 |title=Nine Language Performance Round-up: Benchmarking Math & File I/O {{!}} OSnews |accessdate=28 листопада 2019 |archive-date=28 листопада 2019 |archive-url=https://web.archive.org/web/20191128215101/https://www.osnews.com/story/5602/ }}</ref>

=== Питання реалізації ===
Питання реалізації можуть також вплинути на фактичну ефективність. Це стосується вибору мови програмування і способу, яким алгоритм фактично закодований, вибору [[Компілятор|транслятора]] для вибраної мови або використовуваних опцій компілятора, і навіть [[Операційна система|операційної системи]]. У деяких випадках мова, реалізована у вигляді [[Інтерпретатор|інтерпретатора]], може виявитися істотно повільнішою, ніж мова, реалізована у вигляді компілятора{{Sfn|Floating Point Benchmark}}.

Є й інші чинники, які можуть вплинути на час або використовувану пам'ять, але які виявляються поза контролем програміста. Сюди потрапляють [[вирівнювання даних]], {{Нп|Деталізація даних|деталізація|en|Granularity#Data_granularity}}{{Прояснити}}, [[Збирання сміття|прибирання сміття]], [[паралелізм на рівні команд]] і виклик підпрограм{{Sfn|Steele|1977}}.

Деякі процесори мають здатність виконувати [[Векторний процесор|векторні операції]], що дозволяє однією операцією опрацювати кілька операндів. Може виявитися просто або непросто використовувати такі можливості на рівні програмування або компіляції. Алгоритми, розроблені для послідовних обчислень, можуть зажадати повної переробки для використання [[Паралельні обчислення|паралельних обчислень]] .

Інша проблема може виникнути з сумісністю процесорів, в яких команди можна реалізувати по іншому, так що команди на одних моделях можуть бути відносно повільнішими на інших моделях. Це може виявитися проблемою для [[Оптимізувальний компілятор|оптимізувального компілятора]].

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

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

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

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

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

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

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

=== Час ===

==== Теорія ====
Для [[Теорія алгоритмів|аналізу]] алгоритму зазвичай використовується аналіз [[Часова складність алгоритму|часової складності алгоритму]], щоб оцінити час роботи як функцію від розміру вхідних даних. Результат зазвичай виражається в термінах [[Нотація Ландау|«O» велике]] . Це корисно для порівняння алгоритмів, особливо в разі обробки великої кількості даних. Більш детальні оцінки потрібні для порівняння алгоритмів, коли обсяг даних малий (хоча така ситуація навряд чи викличе проблеми). Алгоритми, які включають паралельні обчислення, можуть виявитися важчими для аналізу.

==== Практика ====
Використовуються порівняльні тести часу роботи алгоритму. Багато мов програмування містять функції, що відображають час використання процесора. Для алгоритмів, що працюють довго, витрачений час також може являти інтерес. Результати в загальному випадку потрібно усереднювати за серією тестів.

Цей вид тестів може бути дуже чутливим до зміни [[Апаратне забезпечення|обладнання]] і можливості роботи інших програм у той самий час у [[Багатопроцесорність|багатопроцесорному]] і [[Багатозадачність|багатозадачному]] середовищі.

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

=== Пам'ять ===
Цей розділ стосується використання основної пам'яті (найчастіше, RAM) потрібної алгоритму. Як і для часового аналізу вище, для [[Теорія алгоритмів|аналізу]] алгоритму зазвичай використовується аналіз {{Нп|DSPACE|просторової складності алгоритму|en|}}, щоб оцінити необхідну пам'ять часу виконання як функцію від розміру входу. Результат зазвичай виражається в термінах [[Нотація Ландау|«O» велике]].

Існує чотири аспекти використання пам'яті:

* Кількість пам'яті, необхідна для зберігання коду алгоритму.
* Кількість пам'яті, необхідна для вхідних даних.
* Кількість пам'яті, необхідна для будь-яких вихідних даних (деякі алгоритми, такі як сортування, часто переставляють вхідні дані і не вимагають додаткової пам'яті для вихідних даних).
* Кількість пам'яті, необхідна для обчислювального процесу під час обчислень (сюди входять іменовані змінні і будь-який стековий простір, необхідний для виклику підпрограм, який може бути суттєвим при використанні [[Рекурсія (програмування)|рекурсії]]).

Ранні електронні комп'ютери і домашні комп'ютери мали відносно малий обсяг робочої пам'яті. Так, в 1949 [[EDSAC]] мав найбільшу робочу пам'ять 1024 17-бітних слів, а в 1980 Sinclair [[ZX80]] випускався з 1024 байтами робочої пам'яті.

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

* Кеш (часто, статична RAM)&nbsp;— працює на швидкостях, порівнянних з [[Центральний процесор|ЦПУ]]
* Основна фізична пам'ять (часто, динамічна RAM)&nbsp;— працює трохи повільніше, ніж ЦПУ
* [[Віртуальна пам'ять]] (найчастіше, на диску)&nbsp;— дає ілюзію величезної пам'яті, але працює в тисячі разів повільніше, ніж RAM.

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

У ранні дні електронних обчислень, якщо алгоритм і його дані не вміщалися в основну пам'ять, він не міг використовуватися. В наші дні використання віртуальної пам'яті забезпечує величезну пам'ять, але за рахунок продуктивності. Якщо алгоритм і його дані вміщаються в кеш, можна отримати дуже високу швидкість, так що мінімізація необхідної пам'яті допомагає мінімізувати час. Алгоритм, який не поміщається повністю в кеш, але забезпечує {{Нп|локальність посилань||en|Locality of reference}}, може працювати порівняно швидко.

== Приклади ефективних алгоритмів ==

* [[Швидке сортування]], перший відомий алгоритм зі швидкістю близько <math>O(n\log n)</math>
* [[Пірамідальне сортування]], інший швидкий алгоритм сортування
* [[Двійковий пошук]] для пошуку в упорядкованій таблиці
* [[Алгоритм Бойєра — Мура|Алгоритм Бойера&nbsp;— Мура]] для пошуку рядка всередині іншого рядка

== Критика поточного стану програмування ==

* {{Нп|Девід Мей (інформатик)|Девід Мей|en|David May (computer scientist)}}, [[Велика Британія|британський]] [[Інформатика|учений в галузі інформатики]], [[професор]] [[Інформатика|інформатики]] [[Бристольський університет|Бристольського університету]], засновник і [[головний інженер]] {{Нп|XMOS|XMOS Semiconductor|en|XMOS}} вважає, що одна з проблем полягає в існуванні віри, що [[закон Мура]] вирішує питання неефективності. Він запропонував «альтернативний» закон Мура ({{Нп|Закон Вірта||ru|Закон Вирта}})<ref>{{Cite web|url=http://www.cs.bris.ac.uk/~dave/iee.pdf|title=Архивированная копия|accessdate=2017-09-14|archiveurl=https://web.archive.org/web/20160303181322/http://www.cs.bris.ac.uk/~dave/iee.pdf|archivedate=2016-03-03|deadlink=yes}}</ref> :

{{Цитата|Програми стають повільнішими більш стрімко, ніж комп'ютери стають швидшими.|3=|4=}}

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

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

* Програміст Адам Н. Розербург у своєму блозі ''«The failure of the Digital computer»,'' описав поточний стан програмування як близький до «Software event horizon» (рівню програмної катастрофи, натяк на фантастичний ''«shoe event horizon»'' (рівень взуттєвої катастрофи), описаний [[Дуглас Адамс|Дугласом Адамсом]] в його книзі «[[Путівник Галактикою|Автостопом по галактиці]]»<ref>{{Cite web |url=http://www.the-adam.com/adam/rantrave/computers.htm |title=Архівована копія |accessdate=28 листопада 2019 |archive-date=23 листопада 2019 |archive-url=https://web.archive.org/web/20191123115350/http://www.the-adam.com/adam/rantrave/computers.htm }}</ref>). Він оцінив падіння продуктивності на 70 dB, або на «99.99999&nbsp;% від можливого», в порівнянні з 1980-ми роками&nbsp;— «коли [[Артур Кларк]] порівняв обчислювальні здатності комп'ютерів 2001 з комп'ютером [[HAL 9000|HAL]] у книзі „[[2001: Космічна Одіссея]]“, він вказав, що на диво малі і потужні були комп'ютери, але програми стали сумно розчаровувати».

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

* [[Wired]]<ref>{{Цитата:Новини|url=https://www.wired.com/magazine/2010/11/mf_algorithmolympics/all/1|work=Wired|first=Jason|last=Fagone|title=Teen Mathletes Do Battle at Algorithm Olympics|date=29 листопада 2010|accessdate=28 листопада 2019|archive-date=16 березня 2014|archive-url=https://web.archive.org/web/20140316232556/http://www.wired.com/magazine/2010/11/mf_algorithmolympics/all/1}}</ref>

== Див. також ==

* [[Теорія алгоритмів|Аналіз алгоритмів]]
* [[Арифметичне кодування]]&nbsp;— вид [[Ентропійне кодування|ентропійного кодування]] {{Нп|зі змінною довжиною коду||en|Variable-length code}} для ефективного стиснення даних
* [[Асоціативний масив]]&nbsp;— структура даних, яку можна зробити більш ефективною при застосуванні [[Базисне дерево|дерев PATRICIA]] або {{Нп|Масив Джуді|масивів Джуді|en|Judy array}}
* [[Тест продуктивності]]&nbsp;— метод вимірювання порівняльного часу виконання в певних випадках
* {{Нп|Найкращий, найгірший і середній випадки||en|Best, worst and average case}}&nbsp;— домовленості щодо оцінки часу виконання за трьома сценаріями
* [[Двійковий пошук]]&nbsp;— проста і ефективна техніка пошуку у відсортованому списку
* {{Нп|Таблиця галуження||en|Branch table}}&nbsp;— техніка скорочення довжини команд, розміру [[Машинний код|машинного коду]], і найчастіше, пам'яті
* [[Оптимізувальний компілятор]]&nbsp;— компілятор, який використовує різні методи отримання більш оптимального програмного коду при збереженні функціональних можливостей
* {{Нп|Обчислювальна складність математичних операцій||en|Computational complexity of mathematical operations}}
* [[Обчислювальна складність]]&nbsp;— поняття в інформатиці, що позначає залежності обсягу роботи від розміру вхідних даних
* [[Обчислювальна потужність комп'ютера]]&nbsp;— кількісна характеристика швидкості виконання операцій на комп'ютері
* [[Стиснення даних]]&nbsp;— скорочення обсягу передаваних даних і займаного дискового простору
* [[Індекс таблиці бази даних|Індекс]]&nbsp;— дані, що збільшують швидкість вибірки даних з таблиць
* [[Ентропійне кодування]]&nbsp;— кодування послідовності значень з можливістю однозначного відновлення з метою зменшення обсягу даних (довжини послідовності) за допомогою усереднення ймовірностей появи елементів у закодованій послідовності
* [[Збирання сміття]]&nbsp;— автоматичне звільнення пам'яті після використання
* [[Зелені інформаційні технології]]&nbsp;— рух за впровадження «зелених» технологій, які споживають менше ресурсів
* [[Код Гаффмана]]&nbsp;— алгоритм ефективного кодування даних
* [http://msdn.microsoft.com/en-us/library/ff647790.aspx Improving Managed code Performance] {{Webarchive|url=https://web.archive.org/web/20171224101732/https://msdn.microsoft.com/en-us/library/ff647790.aspx |date=24 грудня 2017 }}&nbsp;— Microsoft MSDN Library
* [[Локальність посилань]]&nbsp;— щоб уникнути затримок, викликаних [[Кеш процесора|кешуванням]] через доступ до нелокальної пам'яті
* [[Оптимізація циклів]]
* [[Керування пам'яттю]]
* [[Оптимізація (інформатика)]]
* [[Профілювання (програмування)|Аналіз продуктивності]]&nbsp;— методи вимірювання фактичної продуктивності алгоритму в реальному часі
* [[Система реального часу|Обчислення в реальному часі]]&nbsp;— приклад критичних за часом застосунків
* [[Одночасна багатопотоковість]]
* [[Спекулятивне виконання|Випереджувальне виконання]], коли обчислення проводяться, навіть якщо ще невідомо, чи знадобляться їх результати, або {{li|негайне обчислення||Q615541}} як протилежність [[Ліниві обчислення|ледачих обчислень]]
* [[Часова багатопотоковість]]
* [[Шитий код]]&nbsp;— один із способів реалізації проміжної віртуальної машини при інтерпретації мов програмування (поряд з байт-кодом)
* [[Таблиця віртуальних методів]]&nbsp;— механізм підтримки динамічної відповідності (або методу пізнього зв'язування)

== Примітки ==
{{Reflist|32em}}

== Література ==
* {{Cite web
|author=Christopher Green
|title=Classics in the History of Psychology
|url=http://psychclassics.yorku.ca/Lovelace/lovelace.htm
|accessdate=19 травня 2013
|year=2013
|ref=Green, 2013
|archive-date=27 вересня 2013
|archive-url=https://web.archive.org/web/20130927084455/http://psychclassics.yorku.ca/Lovelace/lovelace.htm
}}
* {{статья
 |ref                      = Knuth
 |автор               = Knuth D.
 |заглавие         = Structured Programming with go-to Statements
 |издательство = ACM
 |издание           = Computing Surveys
 |том                   = 6
 |выпуск             = 4
 |год                   = 1974
 |ссылка             = http://pplab.snu.ac.kr/courses/adv_pl05/papers/p261-knuth.pdf
 |archiveurl               = https://web.archive.org/web/20090824073244/http://pplab.snu.ac.kr/courses/adv_pl05/papers/p261-knuth.pdf
 |archivedate              = 2009-08-24
 |url                      = http://pplab.snu.ac.kr/courses/adv_pl05/papers/p261-knuth.pdf
 |deadlink                 = да
}}
* {{cite web
|ref=Benchmark History
|url=http://www.roylongbottom.org.uk/whetstone.htm#anchorPC2
|title=Whetstone Benchmark History
|publisher=Roylongbottom.org.uk
|accessdate=14 грудня 2011
|archive-date=15 січня 2012
|archive-url=https://web.archive.org/web/20120115044741/http://www.roylongbottom.org.uk/whetstone.htm#anchorPC2
}}
* {{cite web 
|ref=Floating Point Benchmark 
|url=http://www.fourmilab.ch/fourmilog/archives/2005-08/000567.html 
|title=Floating Point Benchmark: Comparing Languages (Fourmilog: None Dare Call It Reason) 
|publisher=Fourmilab.ch 
|date=4 серпня 2005 
|accessdate=14 грудня 2011 
|archive-date=11 грудня 2011 
|archive-url=https://web.archive.org/web/20111211060226/http://www.fourmilab.ch/fourmilog/archives/2005-08/000567.html 
}}
* {{стаття
|автор=Guy Lewis Steele, Jr.
|ref=Steele
|назва=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.
|місяць=October
|рік=1977
|посилання=http://dspace.mit.edu/handle/1721.1/5753
}}

== Посилання ==

* [https://web.archive.org/web/20100507182114/http://cgjennings.ca/fjs/index.html Анімація алгоритму Бойєра-Мура] ([[Java-аплет]])
* [https://web.archive.org/web/20121230220150/http://www.dailymotion.com/video/xn8cg8_ted-talk-kevin-slavin-how-algorithms-shape-our-world_tech#.UNqz4axdxlM «How algorithms shape our world».] Виступ Кельвіна Славіна на [[TED (конференція)|TED-конференції]] .
* [https://dx.doi.org/10.1016/j.compedu.2003.07.004 Misconceptions about algorithmic efficiency in high-schools]
{{ВП-портали|Програмування|Інформаційні технології}}
{{Інформатика}}
[[Категорія:Оптимізація програмного забезпечення]]
[[Категорія:Аналіз алгоритмів]]
[[Категорія:Продуктивність комп'ютера]]