Часова складність алгоритму в комп'ютерних науках є обчислювальною складністю алгоритму, яка описує час потрібний для виконання алгоритму. Вона зазвичай визначається шляхом підрахунку кількості елементарних операцій, виконуваних алгоритмом, при цьому вважають, що кожна елементарна операція виконується за фіксовану кількість часу. Таким чином, кількість часу і кількість елементарних операцій, необхідних для виконання алгоритму, відрізняються постійним множником.
Оскільки час роботи алгоритму може відрізнятися на вхідних даних одного розміру, то зазвичай розглядається найгірший випадок складності, який відповідає максимальному часу, необхідного для виконання при вхідних даних заданого розміру. Менш поширеною і, як правило, явно вказаною є [en], яка є середньою величиною часу на вхідні дані даного розміру (це має сенс, оскільки існує лише скінченне число можливих вхідних даних даного розміру). В обох випадках часова складність алгоритму є функцією від розміру вхідних даних. Оскільки ці функції, як правило, важко точно розрахувати, а час роботи у випадку невеликого розміру вхідних даних, не завжди прогнозований, тому зазвичай оцінюють поведінку складності при збільшенні розміру вхідних даних, тобто асимптотичну поведінку складності алгоритму. Це пояснює, чому зазвичай часову складність часто описують за допомогою нотації великого О, зазвичай і т. д., де n відповідає розміру вхідних даних в одиницях вимірювання або в бітах, які потрібні для їх представлення.
Алгоритмічна складність класифікується відповідно до типу функції, яка її описує в нотації великого О. Наприклад, алгоритм зі складністю є алгоритмом лінійної складності, а алгоритм зі складністю для деякої константи є алгоритмом поліноміальної складності.
Таблиця типових часових складностей
У таблиці наведено деякі поширені класи часових складностей. У таблиці, для зручності через poly(x) = xO(1) позначаємо поліном від x.
Назва | Обчислювальна складність | Час виконання (T(n)) | Приклади часу виконання | Приклади алгоритмів |
---|---|---|---|---|
сталий час | O(1) | 10 | Визначенно парності числа (у двійковому запису) | |
обернена Функція Акермана від часу | O(α(n)) | Амортизаційний аналіз на одну операцію з використанням неперетинних множин | ||
повторний логарифмічний час | O(log* n) | Розподілені розфарбовування циклів | ||
двічі логарифмічний | O(log log n) | Час амортизації на одну операцію при використанні обмеженої черги з пріоритетом | ||
логарифмічний час | O(log n) | log n, log(n2) | Двійковий пошук | |
полілогарифмічний час | poly(log n) | (log n)2 | ||
дробовий степінь | O(nc) where 0 < c < 1 | n1/2, n2/3 | Пошук у К-вимірному дереві | |
сублінійний час | O(n/log* n) | n/(log n), n/(log log n) | Пошук усіх простих чисел, менших заданого n, решетом Аткіна | |
лінійний час | O(n) | n | Пошук найбільшого або найменшого елементу невпорядкованого масиву | |
«n log зірочка n» час | O(n log* n) | n log log n | Решето Ератосфена Алгоритм [en] тріангуляції многокутника | |
квазілінійний час | O(n log n) | n log n, log n! | Найшвидше можливе сортування порівняннями; Швидке перетворення Фур'є. | |
квадратичний час | O(n2) | n2 | Сортування бульбашкою; Сортування включенням | |
кубічний час | O(n3) | n3 | Безпосереднє множення двох матриць розміру n×n. Обчислення часткової кореляції. | |
поліноміальний час | P | 2O(log n) = poly(n) | n, n log n, n10 | Алгоритм Кармаркара для лінійного програмування; Тест простоти AKS |
квазіполіноміальний час | QP | 2poly(log n) | nlog log n, nlog n | Відомий O(log2 n)-апроксимаційний алгоритм для пошуку дерева Штейнера. |
саб-експоненціальний час (перше визначення) | SUBEXP | O(2nε) для всіх ε > 0 | O(2log nlog log n) | Якщо прийняти теоретичні гіпотези, BPP міститься в SUBEXP. |
саб-експоненціальний час (друге визначення) | 2o(n) | 2n1/3 | Відомий алгоритм розкладання числа на множники та [en] | |
експоненціальний час (з лінійною експонентою) | 2O(n) | 1.1n, 10n | Вирішення задачі комівояжера за допомогою динамічного програмування | |
експоненціальний час | EXPTIME | 2poly(n) | 2n, 2n2 | Вирішення [en] повним перебором |
факторіальний час | O(n!) | n! | Вирішення задачі комівояжера повним перебором | |
double exponential time | 22poly(n) | 22n | Перевірка на істину твердження в арифметиці Пресбургера |
Сталий час
Кажуть, що алгоритм виконується за сталий час (записується як O(1) час), якщо значення T(n) обмежене величиною, яка не залежить від розміру вхідних даних. Наприклад, доступ до одного елемента у масиві займає сталий час, коли потрібна лише одна операція для знаходження його місця розташування. Аналогічним чином, знаходимо мінімальне значення в масиві, відсортованому у порядку зростання; це буде перший елемент. Проте, пошук мінімального елемента у невпорядкованому масиві не буде операцією, яка виконується за сталий час, бо вона потребує отримання кожного елемента масива для визначення найменшого значення. Отже, цю операцію можна виконати за лінійний час O(n). Якщо ж кількість елементів відома заздалегідь і не змінюється, тоді про такий алгоритм ще можна сказати, що він виконується за сталий час.
Незважаючи на назву «сталий час», час роботи не повинен бути незалежним від розміру вхідних даних, але верхня межа часу роботи повинна бути обмежена незалежно від розміру вхідних даних. Наприклад, завдання «якщо потрібно, то обміняти значення a та b, так, щоб a ≤ b» виконується за сталий час, хоча і залежить від того, чи відразу виконується умова a ≤ b. Це тому, що є стала t, така, що потрібний час завжди не перевищує t.
Далі наведено приклад фрагменту коду, який виконується за сталий час:
int index = 5; int item = list[index]; if (умова) then виконати деяку операцію, яка потребує сталого часу else виконати деяку операцію, яка потребує сталого часу for i = 1 to 100 for j = 1 to 200 виконати деяку операцію, яка потребує сталого часу
Якщо T(n) є O(будь-яка стала), то це еквівалентно T(n) дорівнює O(1).
Лінійний час
Кажуть, що алгоритм виконується за лінійний час або час O(n), коли його складність дорівнює O(n). По простому, це означає, що час виконання зростає щонайбільше лінійно від кількості вхідних даних. Більш точно, це означає, що існує константа c, така, що час виконання буде щонайбільше cn, коли розмір вхідних даних n. Наприклад, час виконання процедури, яка знаходить суму всіх елементів списку, буде пропорційною довжині списку за умови, що час виконання операції додавання є сталим, або, принаймні, обмежений сталою.
Лінійний час є найкращим за часовою складністю у ситуації, коли алгоритм послідовно читає вхідні дані. Тому, так багато досліджень на виявлення алгоритмів, які виконуються за лінійний час або, принаймні, майже за лінійний час. Ці дослідження включають як програмні, так і апаратні методи. Для досягнення цього є декілька апаратних методів заснованих на паралельних обчисленнях. Прикладом цього є асоціативна пам'ять. Концепція лінійного часу використовується в алгоритмах пошуку збігів у текстах, зокрема, в алгоритмі Боєра Мура та [en].
Доквадратичний час
Алгоритм має доквадратичний час, коли час виконання T(n) = o(n2).
Наприклад, простий, заснований на порівнянні алгоритм сортування буде квадратичним (наприклад, сортування включенням), але більш розвинуті алгоритмі можуть мати доквадратичний час виконання (наприклад, сортування Шелла). Немає загальних алгоритмів, які виконуються за лінійний час, проте зміна квадратичного часу на доквадратичний дуже важлива з практичної точки зору.
Поліноміальний час
Кажуть, що алгоритм виконується за поліноміальний час, якщо верхнею межею часу виконання є поліноміальний вираз від розміру вхідних даних алгоритму, тобто, від деякої додатної константи k. Задачі, для яких існує алгоритм розв'язання, що виконується за поліноміальний час, належать до класу складності P, що є центральним питанням в теорії складності обчислень. [en] стверджує, що поліноміальний час є синонімом «здійсненний», «ефективний» або «швидкий».
Деякі приклади алгоритмів поліноміального часу:
- Алгоритм сортування вибором n цілих чисел виконує операцій, де A — константа. Отже, він виконується за час і є поліноміальним алгоритмом.
- Всі основні арифметичні операції (додавання, віднімання, множення, ділення та порівняння) можна виконати за поліноміальний час.
- Максимальне парування в графах можна знайти за поліноміальний час.
Див. також
- L-нотація
- [en] - просторова складність
Примітки
- (2006). Introduction to the Theory of Computation. Course Technology Inc. ISBN .
- Mehlhorn, Kurt; Naher, Stefan (1990). Bounded ordered dictionaries in O(log log N) time and O(n) space. Information Processing Letters. 35 (4): 183—189. doi:10.1016/0020-0190(90)90022-P.
- Babai, László; ; ; Wigderson, Avi (1993). BPP has subexponential time simulations unless EXPTIME has publishable proofs. Computational Complexity. Berlin, New York: Springer-Verlag. 3 (4): 307—318. doi:10.1007/BF01275486.
- Papadimitriou, Christos H. (1994). Computational complexity. Reading, Mass.: Addison-Wesley. ISBN .
- (1965). The intrinsic computational difficulty of functions. Proc. Logic, Methodology, and Philosophy of Science II. North Holland.
В іншому мовному розділі є повніша стаття Time complexity(англ.). Ви можете допомогти, розширивши поточну статтю за допомогою з англійської. (листопад 2023)
|
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Chasova skladnist algoritmu v komp yuternih naukah ye obchislyuvalnoyu skladnistyu algoritmu yaka opisuye chas potribnij dlya vikonannya algoritmu Vona zazvichaj viznachayetsya shlyahom pidrahunku kilkosti elementarnih operacij vikonuvanih algoritmom pri comu vvazhayut sho kozhna elementarna operaciya vikonuyetsya za fiksovanu kilkist chasu Takim chinom kilkist chasu i kilkist elementarnih operacij neobhidnih dlya vikonannya algoritmu vidriznyayutsya postijnim mnozhnikom Grafiki funkcij sho zazvichaj vikoristovuyutsya pri analizi algoritmiv pokazuyuchi kilkist operacij N zalezhno vid rozmiru n vhidnih danih dlya kozhnoyi funkciyi Oskilki chas roboti algoritmu mozhe vidriznyatisya na vhidnih danih odnogo rozmiru to zazvichaj rozglyadayetsya najgirshij vipadok skladnosti yakij vidpovidaye maksimalnomu chasu neobhidnogo dlya vikonannya pri vhidnih danih zadanogo rozmiru Mensh poshirenoyu i yak pravilo yavno vkazanoyu ye en yaka ye serednoyu velichinoyu chasu na vhidni dani danogo rozmiru ce maye sens oskilki isnuye lishe skinchenne chislo mozhlivih vhidnih danih danogo rozmiru V oboh vipadkah chasova skladnist algoritmu ye funkciyeyu vid rozmiru vhidnih danih Oskilki ci funkciyi yak pravilo vazhko tochno rozrahuvati a chas roboti u vipadku nevelikogo rozmiru vhidnih danih ne zavzhdi prognozovanij tomu zazvichaj ocinyuyut povedinku skladnosti pri zbilshenni rozmiru vhidnih danih tobto asimptotichnu povedinku skladnosti algoritmu Ce poyasnyuye chomu zazvichaj chasovu skladnist chasto opisuyut za dopomogoyu notaciyi velikogo O zazvichaj O n displaystyle O n O n log n displaystyle O n log n O n a displaystyle O n alpha O 2 n displaystyle O 2 n i t d de n vidpovidaye rozmiru vhidnih danih v odinicyah vimiryuvannya abo v bitah yaki potribni dlya yih predstavlennya Algoritmichna skladnist klasifikuyetsya vidpovidno do tipu funkciyi yaka yiyi opisuye v notaciyi velikogo O Napriklad algoritm zi skladnistyu O n displaystyle O n ye algoritmom linijnoyi skladnosti a algoritm zi skladnistyu O n a displaystyle O n alpha dlya deyakoyi konstanti a gt 1 displaystyle alpha gt 1 ye algoritmom polinomialnoyi skladnosti Tablicya tipovih chasovih skladnostejU tablici navedeno deyaki poshireni klasi chasovih skladnostej U tablici dlya zruchnosti cherez poly x xO 1 poznachayemo polinom vid x Nazva Obchislyuvalna skladnist Chas vikonannya T n Prikladi chasu vikonannya Prikladi algoritmiv stalij chas O 1 10 Viznachenno parnosti chisla u dvijkovomu zapisu obernena Funkciya Akermana vid chasu O a n Amortizacijnij analiz na odnu operaciyu z vikoristannyam neperetinnih mnozhin povtornij logarifmichnij chas O log n Rozpodileni rozfarbovuvannya cikliv dvichi logarifmichnij O log log n Chas amortizaciyi na odnu operaciyu pri vikoristanni obmezhenoyi chergi z prioritetom logarifmichnij chas O log n log n log n2 Dvijkovij poshuk polilogarifmichnij chas poly log n log n 2 drobovij stepin O nc where 0 lt c lt 1 n1 2 n2 3 Poshuk u K vimirnomu derevi sublinijnij chas O n log n n log n n log log n Poshuk usih prostih chisel menshih zadanogo n reshetom Atkina linijnij chas O n n Poshuk najbilshogo abo najmenshogo elementu nevporyadkovanogo masivu n log zirochka n chas O n log n n log log n Resheto Eratosfena Algoritm en triangulyaciyi mnogokutnika kvazilinijnij chas O n log n n log n log n Najshvidshe mozhlive sortuvannya porivnyannyami Shvidke peretvorennya Fur ye kvadratichnij chas O n2 n2 Sortuvannya bulbashkoyu Sortuvannya vklyuchennyam kubichnij chas O n3 n3 Bezposerednye mnozhennya dvoh matric rozmiru n n Obchislennya chastkovoyi korelyaciyi polinomialnij chas P 2O log n poly n n n log n n10 Algoritm Karmarkara dlya linijnogo programuvannya Test prostoti AKS kvazipolinomialnij chas QP 2poly log n nlog log n nlog n Vidomij O log2 n aproksimacijnij algoritm dlya poshuku dereva Shtejnera sab eksponencialnij chas pershe viznachennya SUBEXP O 2ne dlya vsih e gt 0 O 2log nlog log n Yaksho prijnyati teoretichni gipotezi BPP mistitsya v SUBEXP sab eksponencialnij chas druge viznachennya 2o n 2n1 3 Vidomij algoritm rozkladannya chisla na mnozhniki ta en eksponencialnij chas z linijnoyu eksponentoyu 2O n 1 1n 10n Virishennya zadachi komivoyazhera za dopomogoyu dinamichnogo programuvannya eksponencialnij chas EXPTIME 2poly n 2n 2n2 Virishennya en povnim pereborom faktorialnij chas O n n Virishennya zadachi komivoyazhera povnim pereborom double exponential time 22poly n 22n Perevirka na istinu tverdzhennya v arifmetici PresburgeraStalij chasKazhut sho algoritm vikonuyetsya za stalij chas zapisuyetsya yak O 1 chas yaksho znachennya T n obmezhene velichinoyu yaka ne zalezhit vid rozmiru vhidnih danih Napriklad dostup do odnogo elementa u masivi zajmaye stalij chas koli potribna lishe odna operaciya dlya znahodzhennya jogo miscya roztashuvannya Analogichnim chinom znahodimo minimalne znachennya v masivi vidsortovanomu u poryadku zrostannya ce bude pershij element Prote poshuk minimalnogo elementa u nevporyadkovanomu masivi ne bude operaciyeyu yaka vikonuyetsya za stalij chas bo vona potrebuye otrimannya kozhnogo elementa masiva dlya viznachennya najmenshogo znachennya Otzhe cyu operaciyu mozhna vikonati za linijnij chas O n Yaksho zh kilkist elementiv vidoma zazdalegid i ne zminyuyetsya todi pro takij algoritm she mozhna skazati sho vin vikonuyetsya za stalij chas Nezvazhayuchi na nazvu stalij chas chas roboti ne povinen buti nezalezhnim vid rozmiru vhidnih danih ale verhnya mezha chasu roboti povinna buti obmezhena nezalezhno vid rozmiru vhidnih danih Napriklad zavdannya yaksho potribno to obminyati znachennya a ta b tak shob a b vikonuyetsya za stalij chas hocha i zalezhit vid togo chi vidrazu vikonuyetsya umova a b Ce tomu sho ye stala t taka sho potribnij chas zavzhdi ne perevishuye t Dali navedeno priklad fragmentu kodu yakij vikonuyetsya za stalij chas int index 5 int item list index if umova then vikonati deyaku operaciyu yaka potrebuye stalogo chasu else vikonati deyaku operaciyu yaka potrebuye stalogo chasu for i 1 to 100 for j 1 to 200 vikonati deyaku operaciyu yaka potrebuye stalogo chasu Yaksho T n ye O bud yaka stala to ce ekvivalentno T n dorivnyuye O 1 Linijnij chasKazhut sho algoritm vikonuyetsya za linijnij chas abo chas O n koli jogo skladnist dorivnyuye O n Po prostomu ce oznachaye sho chas vikonannya zrostaye shonajbilshe linijno vid kilkosti vhidnih danih Bilsh tochno ce oznachaye sho isnuye konstanta c taka sho chas vikonannya bude shonajbilshe cn koli rozmir vhidnih danih n Napriklad chas vikonannya proceduri yaka znahodit sumu vsih elementiv spisku bude proporcijnoyu dovzhini spisku za umovi sho chas vikonannya operaciyi dodavannya ye stalim abo prinajmni obmezhenij staloyu Linijnij chas ye najkrashim za chasovoyu skladnistyu u situaciyi koli algoritm poslidovno chitaye vhidni dani Tomu tak bagato doslidzhen na viyavlennya algoritmiv yaki vikonuyutsya za linijnij chas abo prinajmni majzhe za linijnij chas Ci doslidzhennya vklyuchayut yak programni tak i aparatni metodi Dlya dosyagnennya cogo ye dekilka aparatnih metodiv zasnovanih na paralelnih obchislennyah Prikladom cogo ye asociativna pam yat Koncepciya linijnogo chasu vikoristovuyetsya v algoritmah poshuku zbigiv u tekstah zokrema v algoritmi Boyera Mura ta en Dokvadratichnij chasAlgoritm maye dokvadratichnij chas koli chas vikonannya T n o n2 Napriklad prostij zasnovanij na porivnyanni algoritm sortuvannya bude kvadratichnim napriklad sortuvannya vklyuchennyam ale bilsh rozvinuti algoritmi mozhut mati dokvadratichnij chas vikonannya napriklad sortuvannya Shella Nemaye zagalnih algoritmiv yaki vikonuyutsya za linijnij chas prote zmina kvadratichnogo chasu na dokvadratichnij duzhe vazhliva z praktichnoyi tochki zoru Polinomialnij chasKazhut sho algoritm vikonuyetsya za polinomialnij chas yaksho verhneyu mezheyu chasu vikonannya ye polinomialnij viraz vid rozmiru vhidnih danih algoritmu tobto vid deyakoyi dodatnoyi konstanti k Zadachi dlya yakih isnuye algoritm rozv yazannya sho vikonuyetsya za polinomialnij chas nalezhat do klasu skladnosti P sho ye centralnim pitannyam v teoriyi skladnosti obchislen en stverdzhuye sho polinomialnij chas ye sinonimom zdijsnennij efektivnij abo shvidkij Deyaki prikladi algoritmiv polinomialnogo chasu Algoritm sortuvannya viborom n cilih chisel vikonuye A n 2 displaystyle An 2 operacij de A konstanta Otzhe vin vikonuyetsya za chas O n 2 displaystyle O n 2 i ye polinomialnim algoritmom Vsi osnovni arifmetichni operaciyi dodavannya vidnimannya mnozhennya dilennya ta porivnyannya mozhna vikonati za polinomialnij chas Maksimalne paruvannya v grafah mozhna znajti za polinomialnij chas Div takozhL notaciya en prostorova skladnistPrimitki 2006 Introduction to the Theory of Computation Course Technology Inc ISBN 0 619 21764 2 Mehlhorn Kurt Naher Stefan 1990 Bounded ordered dictionaries in O log log N time and O n space Information Processing Letters 35 4 183 189 doi 10 1016 0020 0190 90 90022 P Babai Laszlo Wigderson Avi 1993 BPP has subexponential time simulations unless EXPTIME has publishable proofs Computational Complexity Berlin New York Springer Verlag 3 4 307 318 doi 10 1007 BF01275486 Papadimitriou Christos H 1994 Computational complexity Reading Mass Addison Wesley ISBN 0 201 53082 1 1965 The intrinsic computational difficulty of functions Proc Logic Methodology and Philosophy of Science II North Holland V inshomu movnomu rozdili ye povnisha stattya Time complexity angl Vi mozhete dopomogti rozshirivshi potochnu stattyu za dopomogoyu perekladu z anglijskoyi listopad 2023 Divitis avtoperekladenu versiyu statti z movi anglijska Perekladach povinen rozumiti sho vidpovidalnist za kincevij vmist statti u Vikipediyi nese same avtor redaguvan Onlajn pereklad nadayetsya lishe yak korisnij instrument pereglyadu vmistu zrozumiloyu movoyu Ne vikoristovujte nevichitanij i nevidkorigovanij mashinnij pereklad u stattyah ukrayinskoyi Vikipediyi Mashinnij pereklad Google ye korisnoyu vidpravnoyu tochkoyu dlya perekladu ale perekladacham neobhidno vipravlyati pomilki ta pidtverdzhuvati tochnist perekladu a ne prosto skopiyuvati mashinnij pereklad do ukrayinskoyi Vikipediyi Ne perekladajte tekst yakij vidayetsya nedostovirnim abo neyakisnim Yaksho mozhlivo perevirte tekst za posilannyami podanimi v inshomovnij statti Dokladni rekomendaciyi div Vikipediya Pereklad