Перегляд вихідного коду сторінки Алгоритм

[[Файл:Image-Al-Kitāb al-muḫtaṣar fī ḥisāb al-ğabr wa-l-muqābala.jpg|thumb|200px|Сторінка з «Алгебри» [[аль-Хорезмі]]&nbsp;— перського математика, від імені якого походить слово ''алгоритм''.]]
'''Алгори́тм''' ({{Abbr|латинізов.|Латинізоване написання|}} ''Algorithmi'' за [[Арабська мова|араб.]] ім'ям [[Перси|перського]] [[математик]]а&nbsp; [[аль-Хорезмі]])&nbsp;— набір [[Інструкція (програмування)|інструкцій]], які описують порядок дій виконавця, щоб досягти результату [[розв'язання задач]]і за скінченну кількість дій; система правил виконання дискретного процесу, яка досягає поставленої мети за скінченний час. Для візуалізації алгоритмів часто використовують [[блок-схема|блок-схеми]].

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

Поняття алгоритму належить до підвалин [[Математика|математики]]. Обчислювальні процеси алгоритмічного характеру (як-то арифметичні дії над [[цілі числа|цілими числами]], знаходження [[найбільший спільний дільник|НСД]] двох чисел тощо) відомі людству з глибокої давнини. Проте, чітке поняття алгоритму сформувалося лише на початку [[XX століття]].

Часткова формалізація поняття алгоритму розпочалася зі спроб розв'язати [[задача розв'язності|задачу розв'язності]] ({{lang-de|Entscheidungsproblem}}), яку сформулював [[Давид Гільберт]] у [[1928]]&nbsp;р. Наступні формалізації були необхідні для визначення ефективної обчислювальності<ref>Kleene 1943 in Davis 1965:274</ref> або «ефективного методу»<ref>Rosser 1939 in Davis 1965:225</ref>; до цих формалізацій належать [[процедура рекурсивна|рекурсивні функції]] [[Курт Гедель|Геделя]]-[[Жак Ербран|Ербрана]]-[[Стівен Коул Кліні|Кліні]] 1930, 1934 та 1935 років, [[лямбда-числення|λ-числення]] [[Алонзо Черч]]а 1936&nbsp;р., «[[Машина Поста|Формулювання 1]]» [[Еміль Пост|Еміля Поста]] [[1936]] року, та [[машина Тюрінга]], розроблена [[Алан Тюрінг|Аланом Тюрінгом]] протягом 1936, 1937 та 1939 років.
В методології алгоритм є базисним поняттям і складає основу опису методів. З методології виходить якісно нове поняття алгоритму як оптимальність з наближенням до прогнозованого абсолюту. Зробивши все в послідовності алгоритму за граничних умов задачі маємо ідеальне рішення нагальних проблем науково-практичного характеру. В сучасному світі алгоритм будь-якої діяльності у формалізованому виразі складає основу освіти на прикладах, за подоби. На основі подібності алгоритмів різних сфер діяльності була сформована концепція (теорія) експертних систем.

== Історія ==
Слово «алгоритм» походить від імені [[Перси|перського]] [[математик]]а й [[астроном]]а [[Аль-Хорезмі]]. Приблизно у [[825]]&nbsp;р. він написав [[трактат]], в якому описав вигадану в [[Індія|Індії]] [[Позиційні системи числення|позиційну]] [[десяткова система числення|десяткову систему числення]].

У першій половині [[XII століття]] твір Аль-Хорезмі потрапив до [[Європа|Європи]] в перекладі [[латинська мова|латиною]] під назвою «''Algoritmi de numero Indorum''» («Алгоритми про індійську лічбу»). Вважається, що ''Algoritmi'' відповідає невдалій латинізації імені Аль-Хорезмі, проте через неправильне тлумачення його як [[іменник]]а в [[множина (мовознавство)|множині]], ним стали називати ''метод обчислення''.

[[Файл:Ada lovelace.jpg|thumb|200px|Баронеса [[Ада Лавлейс]], яку вважають першим програмістом.]]

У [[1843]]&nbsp;р. [[Ада Лавлейс]] описала алгоритм обчислення [[числа Бернуллі|чисел Бернуллі]] на [[Аналітична машина|аналітичній машині]] [[Чарлз Беббідж|Беббіджа]]. Цей алгоритм визнано першою [[Комп'ютерна програма|програмою]], спеціально реалізованою, щоб виконуватися на [[Комп'ютер|ЕОМ]], і через це його розробницю вважають першим програмістом, дарма що машина Беббіджа не була сконструйована за життя Ади<ref name="fuegi" />.

З [[1930-ті|1930-х]] рр. починається бурхливий розвиток галузі дослідження алгоритмів та становлення [[інформатика|інформатики]] в її сучасному вигляді. В 1935 році [[Стівен Коул Кліні|Стівен Кліні]] розробив перше формулювання теорії [[рекурсія|рекурсії]] та показав еквівалентність розробленої системи [[частково рекурсивна функція|частково рекурсивним функціям]]. В [[1936]] році незалежно були опубліковані роботи Алана Тюрінга та [[Еміль Пост|Еміля Поста]], в яких наведено схожі системи для визначення поняття алгоритму. А вже в [[1937]] році було доведено еквівалентність різних визначень<ref name="Bauer 2010">(Розділ «Algorithms» в Bauer, 2010)</ref>.

[[Машина Тюрінга]] пропонувала конструкцію, придатну для автоматичної інтерпретації. Побудована під впливом Алана Тюрінга у [[Велика Британія|Великій Британії]] обчислювальна система [[ACE]] (завершена в 1950 році), та системи, побудовані за [[архітектура фон Неймана|архітектурою фон Неймана]] в [[Сполучені Штати Америки|США]] та в інших країнах (в [[СРСР]]&nbsp;— [[Мала електронна обчислювальна машина|МЕОМ]], розроблена в [[1950]] році в [[Інститут електродинаміки НАН України|Інституті електротехніки АН УРСР]] групою вчених під керівництвом [[Лебедєв Сергій Олексійович|Сергія Лебедєва]]), були першими універсальними обчислювальними пристроями, які повністю задовольняли вимоги обчислюваності<ref name="Bauer 2010"/>.

Протягом [[1935]]-[[1960]] років було розроблено численні ідеї та технології, які лягли в основу сучасної [[інформатика|інформатики]].

Формальні засоби для представлення алгоритмів мали не лише теоретичну значущість. Розробка ''[[алгоритмічна мова|алгоритмічних мов]]'' для програмування обчислювальних пристроїв розпочалась в 1951 році з публікації німецького інженера {{не перекладено|Ганс Рутісхаузер|Ганса Рутісхаузера||Heinz Rutishauser}} ({{lang-de|Heinz Rutishauser}}). Спочатку важливою здавалась проблема [[нотація|нотації]], її досліджував [[Ляпунов Олексій Андрійович|Олексій Ляпунов]], але поступово вона відійшла на другий план<ref>(Розділ «Algorithmic Languages» в Bauer, 2010)</ref>.

Перша [[мова програмування]], [[Планкалкюль]] ({{lang-de|Plankalkül}}) була розроблена [[Конрад Цузе|Конрадом Цузе]] в [[1946]] році, але через відсутність [[компілятор]]ів виконання написаних цією мовою програм було неможливим. Опис мови був надрукований у [[1972]] році, а в [[2000]] році був створений компілятор для підмножини мови.<ref>(Розділ 3.2 в O'Regan, 2008)</ref>

В середині [[1950-ті|1950-х]] було розроблено мову програмування [[Фортран]] [[Джон Бекус|Джоном Бекусом]] з [[IBM]]. Наприкінці 1950-х було розроблено [[ALGOL]] та [[COBOL]]; для навчальних цілей [[BASIC]] (1963) та [[Pascal]] (початок [[1970-ті|1970-х]]). Для системного програмування в [[Bell Laboratories]] було розроблено [[Сі (мова програмування)|C]]<ref>(Розділ 3.3 в O'Regan, 2008)</ref>.

[[Лямбда-числення]] дало поштовх до створення наприкінці [[1950-ті|1950-х]] функційної мови програмування [[Лісп]]. На основі ідей Ліспу було створено [[Scheme]]. Мова [[ML]] була розроблена [[Робін Мілнер|Робіном Мілнером]] наприкінці [[1970-ті|1970-х]]. Наприкінці [[1980-ті|1980-х]] була створена мова [[Haskell]]<ref>(Розділ 3.5 в O'Regan, 2008)</ref>.

Під впливом досліджень в галузі [[штучний інтелект|штучного інтелекту]] розроблено парадигму [[логічне програмування|логічного програмування]]. На відміну від [[імперативне програмування|імперативної]] та [[функційне програмування|функційної парадигм]], логічне програмування не вимагає від розробника описувати спосіб розв'язання поставленої задачі. [[Planner]]&nbsp;— перша мова логічного програмування, була розроблена в 1969 році. На початку 1970-х був розроблений [[Пролог (мова програмування)|Пролог]], який згодом став найпоширенішою мовою логічного програмування зі стандартом [[ISO]], затвердженим у [[1995]] році<ref>(Розділ 3.6 в O'Regan, 2008)</ref>.

== Визначення ==

=== Неформальне визначення ===
Кожен алгоритм передбачає існування ''початкових'' (вхідних) даних та в результаті роботи призводить до отримання певного ''результату''. Робота кожного алгоритму відбувається шляхом виконання послідовності деяких елементарних дій. Ці дії називають ''кроками'', а процес їхнього виконання називають ''алгоритмічним процесом.'' В такий спосіб відзначають властивість ''дискретності алгоритму''<ref>(Игошин, с. 314)</ref>.

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

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

Вхідні дані алгоритму можуть бути обмежені набором ''припустимих вхідних даних.'' Застосування алгоритму до неприпустимих вхідних даних може призводити до того, що алгоритм ніколи не зупиниться, або потрапить в тупиковий стан ([[зависання]]) з якого не зможе продовжити виконання.

=== Формальне визначення ===

Різноманітні теоретичні проблеми [[математика|математики]] та прискорення розвитку [[фізика|фізики]] та техніки поставили на порядок денний точніше визначення поняття алгоритму.

Перші спроби уточнення поняття алгоритму та його дослідження здійснювали в першій половині [[XX століття]] Алан Тюрінг, Еміль Пост, [[Жак Ербран]], [[Курт Гедель]], [[Андрій Андрійович Марков|Андрій Марков]], Алонзо Черч. Було розроблено декілька означень поняття алгоритму, але згодом було з'ясовано, що всі вони визначають одне й те саме поняття (див. [[теза Черча]]).<ref>(Игошин, с. 317)</ref>

==== Машина Тюрінга ====
{{Main|Машина Тюрінга}}
[[Файл:TuringBeispielDiskretAnimatedGIF uk.gif|thumb|250px|Схематична ілюстрація роботи машини Тюрінга.]]

Основна ідея, що лежить в основі машини Тюрінга, дуже проста. Машина Тюрінга&nbsp;— це абстрактна машина ([[автомат]]), що працює зі стрічкою окремих комірок, в яких записано символи. Машина також має голівку для запису та читання символів із комірок, яка може рухатись вздовж стрічки. На кожному кроці машина зчитує символ з комірки, на яку вказує голівка, та, на основі зчитаного символу й внутрішнього стану робить наступний крок. При цьому, машина може змінити свій стан, записати інший символ в комірку, або пересунути голівку на одну комірку ліворуч або праворуч.<ref name="gmbm" />

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

Ця теза є [[аксіома|аксіомою]], [[постулат]]ом, і не може бути доведена математичними методами, оскільки алгоритм не є точним математичним поняттям.

==== Рекурсивні функції ====
{{Main|Рекурсивні функції}}
З кожним алгоритмом можна зіставити функцію, яку він обчислює. Однак постає питання, чи можна довільній функції зіставити машину Тюрінга, а якщо ні, то для яких функцій існує алгоритм? Дослідження цих питань призвело до створення в [[1930-ті|1930-х]] роках теорії рекурсивних функцій<ref>(Игошин, розділ 33)</ref>.

Клас обчислюваних функцій було описано в спосіб, що нагадує побудову деякої [[Аксіоматика|аксіоматичної теорії]] на базі системи [[аксіома|аксіом]]. Спочатку було вибрано найпростіші функції, обчислюваність яких очевидна. Потім було сформульовано правила (оператори) побудови нових функцій на основі вже існуючих. Необхідний клас функцій складається з усіх функцій, які можна отримати з найпростіших застосуванням операторів.

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

Доведення того, що клас обчислюваних функцій збігається з обчислюваними за Тюрінгом відбувається в два кроки: спочатку доводять обчислюваність найпростіших функцій на машині Тюрінга, а потім&nbsp;— обчислюваність функцій, отриманих внаслідок застосування операторів.

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

==== Нормальні алгоритми Маркова ====
{{Main|Нормальні алгорифми}}

Нормальні алгоритми Маркова&nbsp;— це система послідовних застосувань [[підстановка|підстановок]], які реалізують певні процедури отримання нових слів з базових, побудованих із [[символ]]ів деякого [[алфавіт]]у. Як і машини Тюрінга, нормальні алгоритми не виконують самих обчислень: вони лише виконують перетворення слів шляхом заміни літер за заданими правилами<ref>[[Енциклопедія кібернетики]], т. '''2''', c. 90-91.</ref>.

''Нормально обчислюваною'' називають функцію, яку можна реалізувати нормальним алгоритмом. Тобто, алгоритмом, який кожне слово з множини припустимих даних функції перетворює на її вихідні значення<ref>(Игошин, розділ 34)</ref>.

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

=== Стохастичні алгоритми ===
{{Main|Стохастичні алгоритми}}

Однак, наведене вище формальне визначення алгоритму в деяких випадках може бути надто строгим. Інколи виникає потреба у використанні [[випадкова величина|випадкових величин]]<ref name=cohen1996 />. Алгоритм, робота якого визначається не лише вхідними даними, але й значеннями отриманими з [[генератор випадкових чисел|генератора випадкових чисел]], називають ''стохастичним'' (або рандомізованим, від {{lang-en|randomized algorithm}})<ref name="mit" />. Формально, такі алгоритми не можна називати ''алгоритмами'' оскільки існує [[ймовірність]] (близька до нуля), що вони не зупиняться. Проте, стохастичні алгоритми часто бувають ефективнішими за детерміновані, а в окремих випадках&nbsp;— єдиним способом розв'язати задачу<ref name="cohen1996" />.

На практиці замість генератора випадкових чисел використовують [[генератор псевдовипадкових чисел]].

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

Деякі дослідники припускають можливість того, що стохастичний алгоритм дасть із певною наперед відомою ймовірністю неправильний результат. Тоді стохастичні алгоритми можна поділити на два типи<ref>(Розділ 12, с. 12-22 в Atallah, 2010)</ref>:
* алгоритми ''типу Лас-Вегас'' завжди дають коректний результат, але час їхньої роботи невизначений.
* алгоритми ''типу Монте-Карло'', на відміну від попередніх, можуть давати неправильні результати з відомою ймовірністю (їх часто називають ''[[Метод Монте-Карло|методами Монте-Карло]]'').

=== Інші формалізації ===

Для деяких задач названі вище формалізми можуть ускладнювати пошук розв'язків та здійснення досліджень. Для подолання перешкод було розроблено як модифікації «класичних» схем, так і створено нові моделі алгоритму. Зокрема, можна назвати:
* {{не перекладено|Багатострічкова машина Тюрінга|багатострічкову||Multitape Turing machine}} та [[Недетермінована машина Тюрінга|недетерміновану машина Тюрінга]];
* [[Регістрова машина|регістрову]] та [[RAM-машина|RAM-машину]]&nbsp;— прототип сучасних [[комп'ютер]]ів та [[віртуальна машина|віртуальних машин]];
* [[Скінченний автомат|Скінченні]] та [[клітинний автомат|клітинні автомати]]
та інші.

== Нумерація алгоритмів ==
Нумерація алгоритмів відіграє важливу роль в їхньому досліджені та аналізі<ref>(Игошин, розділ 36)</ref>.

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

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

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

== Алгоритмічно нерозв'язні задачі ==
{{Main|Алгоритмічно нерозв'язна задача}}

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

Функцію ''f'' називають ''[[Обчислювана функція|обчислюваною]]'' ({{lang-en|computable}}), якщо існує машина Тюрінга, яка обчислює значення ''f'' для всіх елементів множини визначення функції. Якщо такої машини не існує, функцію ''f'' називають ''необчислюваною''. Функція вважатиметься необчислюваною навіть, якщо існують машини Тюрінга, здатні обчислити значення для підмножини з усієї множини вхідних даних<ref name="linz" />.

Випадок, коли результатом обчислення функції ''f'' є булеве значення ''істина'' або ''неправда'' (або множина {0, 1}) називають ''задачею'', яка може бути ''розв'язною'', або ''нерозв'язною'' в залежності від обчислюваності функції ''f''<ref name="linz" />.

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

Однією з перших задач, для якої було доведено нерозв'язність є ''[[проблема зупинки]]''. Формулюється вона наступним чином:
: ''Маючи опис програми для машини Тюрінга, визначити, чи завершить роботу програма за скінченний час, чи працюватиме нескінченно, отримавши будь-які вхідні дані.''<ref name="facts2009" />

Доведення нерозв'язності проблеми зупинки важливе тим, що до неї можна ''звести'' інші задачі. Наприклад, проблему зупинки на порожній стрічці (визначити для заданої машини Тюрінга чи зупиниться вона, будучи запущена на порожній стрічці) можна звести до простої задачі зупинки, довівши, тим самим, її нерозв'язність<ref name="linz" />.

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

=== Доведення коректності ===
{{Main|Формальні методи}}

Разом з поширенням [[інформаційні технології|інформаційних технологій]] збільшився ризик програмних збоїв. Одним зі способів уникнення помилок в алгоритмах та їхніх реалізаціях є доведення коректності систем математичними засобами.

Використання математичного апарату для аналізу алгоритмів та їхньої реалізацій називають [[формальні методи|формальними методами]]. Формальні методи передбачають застосування [[специфікація формальна|формальних специфікацій]] та, зазвичай, набору інструментів для [[синтаксичний аналіз|синтаксичного аналізу]] та доведення властивостей [[специфікація|специфікацій]]. Абстрагування від деталей реалізації дозволяє встановити властивості системи незалежно від її реалізації. Крім того, точність та однозначність математичних тверджень дозволяє уникнути багатозначності та неточності природних мов<ref>(O'Regan, розділ 4.5)</ref>.

За гіпотезою [[Річард Мейс|Річарда Мейса]] «уникнення помилок краще за усунення помилок»<ref>(Розділ 5.3.6 в Enders, 2003)</ref>. За гіпотезою [[Тоні Гоар|Гоара]] «доведення програм розв'язує проблему коректності, документації та сумісності»<ref>(Розділ 5.3.7 в Enders, 2003)</ref>. Доведення коректності програм дозволяє виявляти їхні властивості по відношенню до всього діапазону вхідних даних. Для доведення коректності програм, поняття коректності було розширене на два типи:
* ''Часткова коректність''&nbsp;— програма дає коректний результат для тих випадків, коли вона завершується.
* ''Повна коректність''&nbsp;— програма завершує роботу та видає коректний результат для всіх елементів з діапазону вхідних даних.
Під час доведення коректності порівнюють текст програми зі специфікацією бажаного співвідношення вхідних-вихідних даних. Для доведень типу Гоара ця специфікація має вигляд [[твердження (програмування)|тверджень]], які називають [[передумова (формальні методи)|перед-]] та [[післяумова (формальні методи)|післяумовами]]. В сукупності з самою програмою, їх ще називають [[Трійки Гоара|трійками Гоара]]. Ці твердження записують
: ''P''{''Q''}''R''
де ''P''&nbsp;— це передумова, що має виконуватись перед запуском програми ''Q'', а ''R''&nbsp;— післяумова, правильна після завершення роботи програми.

Формальні методи було успішно застосовано до широкого кола задач, зокрема: розробка [[електронна схема|електронних схем]], [[штучний інтелект|штучного інтелекту]], систем, чутливих до надійності, безпечності, автоматичних систем на [[залізниця|залізниці]], [[верифікація формальна|верифікації]] [[мікропроцесор]]ів, специфікації стандартів та специфікації і верифікації програм<ref>(O'Regan, с. 119)</ref>.

=== Час роботи ===
{{main|Обчислювальна складність}}
[[Файл:Нотация Ландау.svg|thumb|300px|Графіки функцій наведених в таблиці нижче.]]

Поширеним критерієм оцінки алгоритмів є час роботи та порядок зростання тривалості роботи в залежності від обсягу вхідних даних.<ref name="axo1979" />

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

Час, який витрачає алгоритм як функція від розміру задачі ''n'', називають ''часовою складністю'' цього алгоритму ''T''(''n''). [[Асимптотичний аналіз|Асимптотику поведінки]] цієї функції при збільшенні розміру задачі називають ''асимптотичною часовою складністю'', а для її позначення використовують [[нотація Ландау|нотацію Ландау]] (велике ''O'').

Саме асимптотична складність визначає розмір задач, які алгоритм здатен обробити. Наприклад, якщо алгоритм обробляє вхідні дані розміром ''n'' за час ''cn''², де ''c''&nbsp;— деяка стала, то кажуть, що часова складність такого алгоритму ''O''(''n''²).

Часто, під час розробки алгоритму намагаються зменшити асимптотичну часову складність для найгірших випадків. На практиці ж, трапляються випадки, коли достатнім є алгоритм, який «зазвичай» працює швидко.

Грубо кажучи, аналіз середньої асимптотичної часової складності можна поділити на два типи: ''аналітичний'' та ''статистичний.'' Аналітичний метод дає точніші результати, але складний у використанні на практиці. Натомість статистичний метод дозволяє швидше здійснювати аналіз складних задач<ref>(розділ 11 в Atallah, 2010)</ref>.

В наступній таблиці наведено поширені асимптотичні складності з коментарями<ref>(розділ 1 в Atallah, 2010)</ref>.
{{-}}
{| class="wikitable" border="1"
|-
! Складність
! Коментар
! Приклади
|-
| ''O''(1)
| Сталий час роботи не залежно від розміру задачі
| Очікуваний час пошуку в [[Хеш-таблиця|хеші]]
|-
| ''O''(log&nbsp;log&nbsp;''n'')
| Дуже повільне зростання необхідного часу
| Очікуваний час роботи [[Інтерполяційний алгоритм пошуку|інтерполюючого пошуку]] ''n'' елементів
|-
| ''O''(log&nbsp;''n'')
| Логарифмічне зростання&nbsp;— подвоєння розміру задачі збільшує час роботи на сталу величину
| Обчислення ''x''<sup>''n''</sup>; [[двійковий пошук]] в масиві з ''n'' елементів
|-
| ''O''(''n'')
| Лінійне зростання&nbsp;— подвоєння розміру задачі подвоїть і необхідний час
| Додавання/віднімання чисел з ''n'' цифр; [[лінійний пошук]] в масиві з ''n'' елементів
|-
| ''O''(''n''&nbsp;log&nbsp;''n'')
| Лінеаритмічне зростання&nbsp;— подвоєння розміру задачі збільшить необхідний час трохи більше ніж вдвічі
| [[Сортування злиттям]] або [[Пірамідальне сортування|купою]] ''n'' елементів; нижня границя сортування порівнянням ''n'' елементів
|-
| ''O''(''n''²)
| Квадратичне зростання&nbsp;— подвоєння розміру задачі вчетверо збільшує необхідний час
| Елементарні [[алгоритми сортування]]
|-
| ''O''(''n''³)
| Кубічне зростання&nbsp;— подвоєння розміру задачі збільшує необхідний час у вісім разів
| Звичайне множення матриць
|-
| ''O''(''c''<sup>''n''</sup>)
| Експоненціальне зростання&nbsp;— збільшення розміру задачі на 1 призводить до ''c''-кратного збільшення необхідного часу; подвоєння розміру задачі підносить необхідний час у квадрат
| Деякі [[задача комівояжера|задачі комівояжера]], алгоритми пошуку повним перебором
|}

== Представлення алгоритмів ==
[[Файл:Block-shema.svg|thumb|250px|[[Блок-схема]] алгоритму визначення [[дієвідміна|дієвідміни]] в [[дієслово|дієслові]].]]
У процесі розробки алгоритму можуть використовуватись різні способи його опису, які відрізняються за простотою, наочністю, компактністю, мірою формалізації, орієнтації на машинну реалізацію тощо<ref name="vasylkiv2005" />.

Форми запису алгоритму:
* словесна або вербальна (мовна, формульно-словесна);
* [[псевдокод]] (формальні [[алгоритмічна мова|алгоритмічні мови]]);
* [[схема (інформатика)|схемна]]:
** {{не перекладено|Структурограма|структурограми||Nassi–Shneiderman diagram}} (схеми Нассі-Шнайдермана);
** графічна ([[блок-схема]], виконується за вимогами стандарту).

== Властивості алгоритмів ==

Алгоритми мають ряд важливих властивостей:<ref>Кнут, т. 1,</ref>
;Скінченність: алгоритм має завжди завершуватись після виконання скінченної кількості кроків. Процедуру, яка має решту характеристик алгоритму, без, можливо, скінченності, називають ''методом обчислень''.
;Дискретність: процес, що визначається алгоритмом, можна розчленувати (розділити) на окремі елементарні етапи (кроки), кожен з яких називається кроком алгоритмічного процесу чи алгоритму.<ref name="vasylkiv2005"/>
;Визначеність: кожен крок алгоритму має бути точно визначений. Дії, які необхідно здійснити, повинні бути чітко та недвозначно визначені для кожного можливого випадку.
;Вхідні дані: алгоритм має деяку кількість (можливо, нульову) вхідних даних, тобто, величин, заданих до початку його роботи або значення яких визначають під час роботи алгоритму.
;Вихідні дані: алгоритм має одне або декілька вихідних даних, тобто, величин, що мають досить визначений зв'язок із вхідними даними.
;Ефективність: Алгоритм вважають ефективним, якщо всі його оператори досить прості для того, аби їх можна було точно виконати за скінченний проміжок часу з допомогою олівця та аркушу паперу.
;Масовість: властивість алгоритму, яка полягає в тому, що алгоритм повинен забезпечувати розв'язання будь-якої задачі з класу однотипних задач за будь-якими вхідними даними, що належать до області застосування алгоритму.

== Приклад ==

Як приклад можна навести [[алгоритм Евкліда]].

Алгоритм Евкліда&nbsp;— ефективний метод обчислення [[найбільший спільний дільник|найбільшого спільного дільника]] (НСД). Названий на честь [[Греція|грецького]] [[математика]] [[Евклід]]а, один з найдавніших алгоритмів, що досі використовують<ref name="knuth2" />. Описаний в [[Начала Евкліда|Началах Евкліда]] (приблизно [[300 до н. е.]]), а саме, в книгах VII та X. У сьомій книзі алгоритм описано для [[цілі числа|цілих чисел]], а в десятій&nbsp;— для довжин відрізків.

Існує декілька варіантів алгоритму, нижче записано в [[псевдокод]]і [[рекурсія|рекурсивний]] варіант:

 '''функція''' нсд(a, b)
     '''якщо''' b = 0
        '''поверни''' a
     '''інакше'''
        '''поверни''' нсд(b, a '''mod''' b)

== Див. також ==
{{Портал|Математика}}
* [[Методи розробки алгоритмів]]
* [[Теорія алгоритмів]]
* [[Список алгоритмів]]
* [[Базові алгоритмічні структури]]
* [[Проблема зупинки та алгоритмічна нерозв'язність]]
* [[Структури даних]]
* [[Програмування]]
* [[Хвильовий алгоритм]]

== Джерела та література ==

=== Українською ===
* [https://vue.gov.ua/Алгоритм Алгоритм] // [[ВУЕ]]
* «[[Українська радянська енциклопедія]]» / ред. М. Бажан; 2-е видання.&nbsp;— К., 1974—1985, том 1, ''Алгоритм''.
* «[[Енциклопедія кібернетики]]», відповідальний ред. [[Глушков Віктор Михайлович|В. Глушков]], 1 тт., [[1973]], ''Алгоритм''.
* [http://esu.com.ua/search_articles.php?id=43598  Алгоритм] //[[ЕСУ]]
* {{книга
|автор          = Микола Глибовець
|видавництво    = Видавничий дім «Києво-Могилянська Академія»
|рік            = 2003
|сторінок       = 452
|заголовок      = [http://publish-ukma.kiev.ua/ua/katalog/matematika-prirodnichi-ta-komp-yuterni-nauki/81-osnovi-komp-yuternih-algoritmiv.html Основи комп'ютерних алгоритмів]
|isbn           = 978-966-518-193-9
}}

=== Іншими мовами ===
==== Класичні підручники ====
* {{книга |автор             = [[Вірт Ніклаус|Ніклаус Вірт]]
 |видання         = 1-е
 |видавництво = Prentice Hall
 |рік                 = 1976
 |сторінок       = 366
 |заголовок     = Algorithms + Data Structures = Programs
 |isbn                   = 978-0130224187
 |url-access             = registration
 |url                    = https://archive.org/details/algorithmsdatast00wirt
}} {{ref-en}}
* {{книга
|автор          = [[Дональд Кнут]]
|заголовок      = The Art of Computer Programming
|видання        = 3-е
|видавництво    = Addison-Wesley Professional
|рік            = 1997
|том            = vol.1. Fundamental Algorithms
|сторінок       = 672
|isbn           = 978-0201896831
}} {{ref-en}}
* {{книга
|автор          = [[Дональд Кнут]]
|заголовок      = The Art of Computer Programming
|видання        = 3-е
|видавництво    = Addison-Wesley Professional
|рік            = 1997
|том            = vol.2. Seminumerical Algorithms
|сторінок       = 784
|isbn           = 978-0201896848
}} {{ref-en}}
* {{книга
|автор          = [[Дональд Кнут]]
|заголовок      = The Art of Computer Programming
|видання        = 2-ге
|видавництво    = Addison-Wesley Professional
|рік            = 1998
|том            = vol.3. Sorting and Searching
|сторінок       = 800
|isbn           = 978-0201896855
}} {{ref-en}}

==== Історія ====
* {{книга
|автор          = Gerard O'Regan
|заголовок      = A Brief History of Computing
|видавництво    = Springer
|рік            = 2008
|isbn           = 978-1-84800-083-4
}} {{ref-en}}
* {{книга
|автор          = Friedrich L. Bauer
|заголовок      = Origins and Foundations of Computing
|оригінал       = Kurze Geschichte der Informatik
|видавництво    = Springer
|рік            = 2010
|isbn           = 978-3-642-02991-2
}} {{ref-en}}

==== Каталоги алгоритмів ====
* {{книга
|автор=Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein
|рік=2009
|назва=Introduction to Algorithms
|видання=3
|сторінок=1312
|видавництво=MIT Press
|isbn=978-0262033848}} {{ref-en}}
* {{книга
|автор          = за ред. Ming-Yang Kao
|заголовок      = Encyclopedia of Algorithms
|серія          = Springer Reference
|видавництво    = Springer
|рік            = 2008
|isbn           = 978-0-387-30162-4
}} {{ref-en}}
* {{книга
|автор          = за ред. Mikhail J. Atallah та Marina Blanton
|заголовок      = Algorithms and theory of computation handbook. General concepts and techniques
|видання        = 2-ге
|видавництво    = Chapman & Hall/CRC
|рік            = 2010
|серія          = applied algorithms and data structures
|isbn           = 978-1-58488-822-2
}} та другий том ISBN 978-1-58488-820-8 {{ref-en}}

{{refbegin}}
* {{cite book|last=Davis|first=Martin|authorlink=Мартін Девіс|title=The Undecidable: Basic Papers On Undecidable Propositions, Unsolvable Problems and Computable Functions|publisher=Raven Press|location=New York|year=1965|isbn=0486432289}} {{ref-en}}
* {{cite book|title=Математическая логика и теория алгоритмов|author=Игошин В. И.|edition=2-ге|publisher=Academia|year=2008|місце=Москва|isbn=978-5-7695-4593-1}} {{ref-ru}}
* {{книга
|автор          = за ред. Mikhail J. Atallah та Marina Blanton
|заголовок      = Algorithms and theory of computation handbook. General concepts and techniques
|видання        = 2-ге
|видавництво    = Chapman & Hall/CRC
|рік            = 2010
|серія          = applied algorithms and data structures
|isbn           = 978-1-58488-822-2
}} {{ref-en}}
* {{книга
|автор          = Albert Endres, Dieter Rombach
|заголовок      = A Handbook of Software and Systems Engineering
|серія          = The Fraunhofer IESE Series on Software Engineering
|видавництво    = Addison Wesley
|рік            = 2003
|isbn           = 0-321-15420-7
}} {{ref-en}}
* {{книга
|автор          = Gerard O'Regan
|заголовок      = A Brief History of Computing
|частина        = 4.5
|видавництво    = Springer
|рік            = 2008
|isbn           =  978-1-84800-083-4
}} {{ref-en}}
* {{книга
|автор          = Friedrich L. Bauer
|заголовок      = Origins and Foundations of Computing
|оригінал       = Kurze Geschichte der Informatik
|видавництво    = Springer
|рік            = 2010
|isbn           = 978-3-642-02991-2
}} {{ref-en}}
{{refend}}

== Примітки ==

{{reflist|refs=
<ref name="fuegi">Fuegi, J. and Francis, J. «Lovelace & Babbage and the creation of the 1843 'notes'.» Annals of the History of Computing 25 #4 (October-December 2003): [http://dx.doi.org/10.1109/MAHC.2003.1253887 Digital Object Identifier]</ref>
<ref name="knuth2">{{cite book
|author         = [[Дональд Кнут|Knuth D]]
|year           = 1997
|title          = [[Мистецтво програмування|The Art of Computer Programming]], Volume 2: Seminumerical Algorithms
|edition        = 3rd
|publisher      = Addison–Wesley
|isbn           = 0201896842}}</ref>
<ref name="gmbm">{{cite web
 |work        = Good Math, Bad Math
 |url         = http://scienceblogs.com/goodmath/2007/02/basics_the_turing_machine_with_1.php
 |title       = Basics: The Turing Machine (with an interpreter!
 |date        = 2007-02-09
 |archiveurl  = https://www.webcitation.org/659x9ts9V?url=http://scienceblogs.com/goodmath/2007/02/basics_the_turing_machine_with_1.php
 |archivedate = 2012-02-02
 |accessdate  = 2010-03-03
 |deadurl     = yes
}}</ref>
<ref name="mit">{{cite book
|автор          = Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rives't, Clifford Stein
|рік            = 2001
|назва          = Introduction to Algorithms
| розділ= 5.1
|видання        = 2-ге
|сторінки       = 531
|видавництво    = MIT Press
|isbn           = 0-262-03293-7}}</ref>
<ref name="cohen1996">«Probabilistic algorithms should not be mistaken with methods (which I refuse to call algorithms), which produce a result which has a high probability of being correct. It is essential that an algorithm produces correct results (discounting human or computer errors), even if this happens after a very long time.» {{cite book
|author         = Henri Cohen
|year           = 1996
|title          = A Course in Computational Algebraic Number Theory
|publisher      = Springer-Verlag
|page           = 2
|isbn           = 3-540-55640-0}}</ref>
<ref name="linz">{{книга |автор             = Peter Linz
 |частина         = 12.1
 |заголовок     = An Introduction to Formal Languages and Automata
 |видання         = 3-тє
 |видавництво = Jones and Bartlett Publishers
 |рік                 = 2000
 |isbn                   = 0-7637-1422-4
 |url-access             = registration
 |url                    = https://archive.org/details/introductiontofo00lin_9o9
}}</ref>
<ref name="facts2009">{{cite encyclopedia
 | year = 2009
| title = computability and complexity
 | encyclopedia =  Encyclopedia of computer Science and Technology
| publisher = Facts On File
 | isbn =  978-0-8160-6382-6
 | quote = Given any computer program, can you determine whether the program will halt (end) given any input?
}}</ref>
<ref name="axo1979">{{книга|
назва=Построение и анализ вычислительных алгоритмов|
оригінал=The Design and Analysis of Computer Algorithms|
розділ=1|
автор=[[Альфред Ахо|А. Ахо]], [[Джон Хопкрофт|Дж. Хопкрофт]], [[Джеффрі Ульман|Дж. Ульман]]|
видавництво=«Мир»|
рік=1979|
місце=Москва}}</ref>
<ref name="vasylkiv2005">{{книга
|автор          = Н. М. Васильків, Л. О. Васильків
|заголовок      = Опорний конспект лекцій з дисципліни «Основи алгоритмізації» спеціальність «Комп'ютерні системи та мережі»
|посилання      = http://www.library.tane.edu.ua/files/EVD/IV_06/ALGMET.pdf
|місце          = Тернопіль 
|видавництво    = [[Економічна думка (видавництво)|Економічна думка]]
|рік            = 2005
|сторінок       = 32
}}</ref>
}}

{{добра стаття}}

{{Інформатика}}

[[Категорія:Алгоритми| ]]
[[Категорія:Теорія алгоритмів]]
[[Категорія:Надпопулярні статті]]
[[Категорія:Теоретична інформатика]]
[[Категорія:Комп'ютерна термінологія]]
[[Категорія:Математична логіка]]