Analýza složitosti algoritmů

Analýza složitosti algoritmu se skládá z formálního studia množství zdrojů (například z doby nebo z prostoru ) nezbytné k provedení tohoto algoritmu . To by nemělo být zaměňováno s teorií složitosti , která studuje vnitřní obtížnost problémů a nezaměřuje se na konkrétní algoritmus.

Dějiny

Když vědci chtěli formálně a důsledně konstatovat, jaká je účinnost algoritmu nebo naopak jeho složitost , uvědomili si, že srovnání algoritmů mezi nimi je nezbytné a že nástroje k tomu jsou nezbytné. Éra byla primitivní. V pravěku výpočetní techniky (padesátá léta) bylo publikované měření, pokud existovalo, často závislé na použitém procesoru , dobách přístupu RAM a velkokapacitní paměti , použitém programovacím jazyce a použitém překladači .

K posouzení účinnosti algoritmů byl proto nezbytný přístup nezávislý na hardwaru. Donald Knuth byl jedním z prvních, kdo jej systematicky aplikoval od prvních svazků své série The Art of Computer Programming . Tuto analýzu doplnil úvahami specifickými pro teorii informací : tato například v kombinaci se Stirlingovým vzorcem ukazuje, že v nejhorším případě není možné na počítačovém vektoru provést obecný třídění (to znamená , pouze v porovnání) N prvků v rostoucí dobou s N pomalejší než N ln N .

Různé přístupy

Nejvíce klasický přístup je tudíž pro výpočet výpočet čas v nejhorším případě .

K analýze složitosti v nejhorším případě existují nejméně tři alternativy. Průměrná složitost algoritmů, založené na pravděpodobnostní distribuci velikostí dat, pokusy odhadnout průměrnou dobu, po kterou lze očekávat na základě vyhodnocení algoritmu na základě údajů o určité velikosti. Zůstatkové složitost datových struktur spočívá ve stanovení nákladů na sekvence operací. Cílem novější analýzy plynulého algoritmu je přiblížit se reálným situacím výpočtem složitosti v nejhorším případě na mírně hlučných případech.

Příklad hledání v seřazeném seznamu

Předpokládejme, že problém spočívá v nalezení jména v telefonním seznamu, který se skládá ze seznamu seřazeného podle abecedy. Lze to provést mnoha různými způsoby. Tady jsou dvě:

Lineární vyhledávání : procházejte stránky v (abecedním) pořadí, dokud nenajdete hledané jméno.
Dichotomické vyhledávání : otevřete adresář uprostřed, pokud je nalezené jméno v abecedním pořadí než hledané, podívejte se dříve, jinak se postarejte. Opakujte operaci, která spočívá ve vyjmutí polovičních adresářů (pak čtvrtinářových, poté osmých adresářů atd.), Dokud nenajdete hledané jméno.

Pro každou z těchto metod existuje nejhorší a nejlepší případ. Zvažte metodu 1:

Nejlepší je, když je název první v adresáři, poté se název okamžitě najde.
Nejhorším scénářem je situace, kdy je název poslední v adresáři, poté se název najde po procházení všech jmen.

Pokud adresář obsahuje 30 000 jmen, bude nejhorší případ vyžadovat 30 000 kroků. Nejhorší složitost této první metody pro položky v poskytnutém adresáři je , to znamená, že v nejhorším případě je doba výpočtu řádově velká : musíte procházet všechna jména jeden po druhém. $ne$ $My)$ $ne$ $ne$

Druhý algoritmus požádá v nejhorším případě o rozdělení adresáře na dvě části, poté o rozdělení této dílčí části na dvě části atd., Dokud nebudete mít pouze jedno jméno. Počet potřebných kroků bude celé číslo, které je okamžitě větší než které, když je 30 000, je 15 (protože je 32 768). Složitost (počet operací) tohoto druhého algoritmu v nejhorším případě je pak , což znamená, že řádem počtu operací v tomto nejhorším případě je logaritmus založený na velikosti l 'adresáře, tj. řekněte, že pro adresář, jehož velikost je mezi a , bude řádově . Můžeme také psát nebo , protože a máme stejnou velikost. $\ log _ {2} \, n$ $ne$ $2 ^ {{15}}$ $O (\ log _ {2} \, n)$ $2$ $2 ^ {{p-1}}$ $2 ^ {{p}}$ $p$ $O (\ ln \, n)$ $O (\ log _ {2} \, n)$ $\ ln \, n$ $\ log _ {2} \, n$

Složitost, komparativní

Abychom získali představu o různých složitostech, níže uvedená tabulka představuje různé třídy složitosti, jejich název, referenční doby provádění a problém uvedené složitosti. Doby provedení se odhadují na základě přístupu do paměti 10 nanosekund na krok. Časy zde prezentované nemají žádnou realistickou hodnotu, protože během provádění na stroji vstupuje do hry mnoho mechanismů. Časy jsou uvedeny jako indikace pro poskytnutí řádové hodnoty času potřebného pro provedení takového nebo takového algoritmu.

Řád času potřebného k provedení algoritmu typu složitosti

Čas	Typ složitosti	Čas pro n = 5	Čas pro n = 10	Čas pro n = 20	Čas pro n = 50	Čas pro n = 250	Čas pro n = 1000	Čas pro n = 10 000	Čas pro n = 1 000 000	Příklad problému
$O (1)$	neustálá složitost	10 ns	10 ns	10 ns	10 ns	10 ns	10 ns	10 ns	10 ns	přístup k buňce tabulky
$O (\ log (n))$	logaritmická složitost	10 ns	10 ns	10 ns	20 ns	30 ns	30 ns	40 ns	60 ns	dichotomické vyhledávání
$\ scriptstyle O ({\ sqrt {n}})$	složitost kořenů	22 ns	32 ns	45 ns	71 ns	158 ns	316 ns	1 µs	10 µs	naivní test primality
$My)$	lineární složitost	50 ns	100 ns	200 ns	500 ns	2,5 us	10 µs	100 µs	10 ms	Seznam kurzů
$\ scriptstyle O (n \; log ^ {*} (n))$	kvazilineární složitost	50 ns	100 ns	200 ns	501 ns	2,5 us	10 µs	100,5 µs	10,05 ms	Delaunayova triangulace
$O (n \ log (n))$	lineární složitost	40 ns	100 ns	260 ns	850 ns	6 µs	30 µs	400 µs	60 ms	optimální porovnání (například sloučení nebo haldy )
$O (n ^ {{2}})$	kvadratická složitost (polynom)	250 ns	1 µs	4 µs	25 µs	625 µs	10 ms	1 s	2,8 hodiny	Procházení 2D polí
$O (n ^ {{3}})$	kubická složitost (polynom)	1,25 us	10 µs	80 µs	1,25 ms	156 ms	10s	2,7 hodiny	316 let	množení naivní matice
$2 ^ {{{\ rm {{poly} (\ log (n))}}}}$	subexponenciální složitost	30 ns	100 ns	492 ns	7 µs	5 ms	10s	3,2 roku	$10 ^ {20}$ let	faktorizace celých čísel pomocí GNFS (nejlepší algoritmus známý v roce 2018)
$2 ^ {{{\ rm {{poly} (n)}}}}$	exponenciální složitost	320 ns	10 µs	10 ms	130 dní	$10 ^ {{59}}$ let	...	...	...	problém s batohem hrubou silou
$My!)$	složitost faktorů	1,2 us	36 ms	770 let	$10 ^ {{48}}$ let	...	...	...	...	problém obchodního cestujícího s naivním přístupem
$2 ^ {{2 ^ {{{\ rm {{poly} (n)}}}}}}$	dvojnásobně exponenciální složitost	4,3 s	$10 ^ {{278}}$ let	...	...	...	...	...	...	Presburgerovo aritmetické rozhodnutí

$log ^ {*} (n)$ je iterovaný logaritmus .

Poznámky

Od Donalda Knutha The Dangers of Computer Science Theory , in Selected Papers on Analysis of Algorithms (CSLI Lecture Notes, no. 102.) ( ISBN 1-57586-212-3 ) , první dílo toho, co se nyní nazývá teorie výpočetní složitosti je Demuthova práce z roku 1956: HB Demuth, Electronic Data Sorting - Phh thesis, Stanford University (1956) -, 92 stran, Částečně reprodukováno v IEEE Transactions on Computer (1985), str. 296-310.

Bibliografie

Olivier Carton , Formální jazyky, vypočítatelnost a složitost ,2008[ detail vydání ] ( číst online )
(en) Sanjeev Arora a Boaz Barak , Výpočetní složitost: moderní přístup , Cambridge University Press ,2009( ISBN 0-521-42426-7 )
(en) Christos Papadimitriou , Computational Complexity , Addison-Wesley ,1993( ISBN 978-0-201-53082-7 )
(en) Michael R. Garey a David S. Johnson, Computers and Intractability: A Guide to the theory of NP-completeness , WH Freeman & Company, 1979 ( ISBN 0-7167-1045-5 )
Richard Lassaigne a Michel de Rougemont, Logic and Complexity , Hermes, 1996 ( ISBN 2-86601-496-0 )
Nicolas Hermann a Pierre Lescanne, je P = NP? The Research Files, 20: 64–68, srpenŘíjna 2005

Podívejte se také

Související články

Teorie složitosti (teoretická informatika)
Složitost , obecný článek o složitosti
Kolmogorovova složitost
Kombinatorická exploze
Nedeterministický Turingův stroj
Polynomiální redukce