O-mare

Exemplu de notație mare-O: f (x) ∈ O (g (x)), există c > 0 și o valoare x ₀ astfel încât în dreapta lui x ₀ avem f (x) <cg (x)

Notația matematică mare-O este utilizată pentru a descrie comportamentul asimptotic al funcțiilor . Scopul său este de a caracteriza comportamentul unei funcții pentru argumente ridicate într-un mod simplu, dar riguros, pentru a putea compara comportamentul mai multor funcții între ele. Mai precis, este folosit pentru a descrie o limită superioară asimptotică pentru magnitudinea unei funcții față de alta, care are de obicei o formă mai simplă. Are două domenii principale de aplicare: în matematică , este de obicei folosit pentru a caracteriza restul trunchierii unei serii infinite, în special a unei serii asimptotice , în timp ce în informatică este util în analiza complexității algoritmilor .

În utilizarea informală, notația O este utilizată în mod obișnuit pentru a descrie o limită asimptotică îngustă , dar limitele asimptotice strânse sunt mai formal și corect indicate prin litera Θ (Theta mare), așa cum este descris mai jos.

Istorie

Această notație a fost introdusă pentru prima dată de teoreticianul german al numerelor Paul Bachmann în 1894 ^[1] , în al doilea volum al cărții Analytische Zahlentheorie („Teoria analitică a numerelor”), al cărei prim volum (care încă nu conținea notația O -grande) a apărut în 1892 . Notarea a devenit populară datorită lucrării unui alt teoretician al numerelor german, Edmund Landau ^[2] , motiv pentru care astăzi este uneori numit simbolul Landau . O mare, care înseamnă „de ordinul lui”, a fost inițial un omicron capital; astăzi se folosește și litera mare O , dar niciodată cifra zero .

Utilizare

Există două utilizări pentru această notație, care sunt formal apropiate, dar clar diferite: asimptotele infinite și asimptotele infinitesimale . Această distincție este doar aplicativă și nu de principiu. Cu toate acestea, definiția formală a „Big-O” este aceeași în ambele cazuri, cu singura diferență în valoarea la care se intenționează să se aplice limita funcției la care „Big-O” se aplică.

Comportamentul asimptotic la infinit

Notația O mare este utilă în analiza eficienței algoritmilor. De exemplu, să presupunem că am descoperit că timpul (sau numărul de pași) necesar pentru a finaliza o problemă de dimensiune n este T ( n ) = 4 n ² - 2 n + 2.

Pentru valori mari ale lui n, termenul n ² va deveni preponderentă în raport cu ceilalți, care nu pot fi luate în considerare; de exemplu, pentru n egal cu 500, termenul de 4 n ² va fi egală cu 1000 de ori termenul de 2 n și ignorându din urmă va fi, în cele mai multe cazuri, să fie o aproximare tolerabil.

Mai mult, chiar și coeficienții devin irelevanți dacă comparăm expresia anterioară cu una de ordin superior, cum ar fi una care conține un termen n³ sau 2 ⁿ . Dacă și T ( n ) = 1.000.000 n ², dacă U ( n ) = n ³, U ( n ) va fi totuși mai mare decât T ( n ) pentru n mai mare de 1.000.000 ( T (1.000.000) = 1.000 .000³ = U ( 1.000.000)).

Notația big-O reușește să exprime doar acest concept: vom scrie

T(n)\in O(n^{2})

{\ displaystyle T (n) \ în O (n ^ {2})}

T (n) \ în O (n ^ {2})

și vom spune că algoritmul are o complexitate temporală de ordinul lui n ² .

Mare-O și infinitesimal

Notația Big-O poate fi utilizată și pentru a descrie termenul de eroare într-o aproximare a unei funcții. De exemplu,

e^{x}=1+x+{\frac {x^{2}}{2}}+O(x^{3})\qquad {\hbox{per}}\ x\to 0

{\ displaystyle e ^ {x} = 1 + x + {\ frac {x ^ {2}} {2}} + O (x ^ {3}) \ qquad {\ hbox {per}} \ x \ to 0 }

și ^ {x} = 1 + x + {\ frac {x ^ {2}} {2}} + O (x ^ {3}) \ qquad {\ hbox {per}} \ x \ to 0

exprimă faptul că diferența $e^{x}-\left(1+x+{\frac {x^{2}}{2}}\right)$ ${\ displaystyle e ^ {x} - \ left (1 + x + {\ frac {x ^ {2}} {2}} \ right)}$ $e ^ {x} - \ left (1 + x + {\ frac {x ^ {2}} {2}} \ right)$ este mai mică în valoare absolută decât o constantă pozitivă înmulțită cu $|x|^{3}$ ${\ displaystyle | x | ^ {3}}$ $| x | ^ {3}$ când x este suficient de aproape de 0.

Definiție formală

Asuma ca $f(x)$ ${\ displaystyle f (x)}$ $f (x)$ Și $g(x)$ ${\ displaystyle g (x)}$ $g (x)$ sunt două funcții definite pe un subset de numere reale ^[3] . Să spunem asta

f(x)\in O(g(x))

{\ displaystyle f (x) \ în O (g (x))}

{\ displaystyle f (x) \ în O (g (x))}

pentru

x\to \infty

{\ displaystyle x \ to \ infty}

{\ displaystyle x \ to \ infty}

dacă și numai dacă

\exists \;x_{0}\in \mathbb {R} ,\;c>0\quad :\quad |f(x)|\leq c|g(x)|\quad \forall x>x_{0}\;

{\ displaystyle \ există \; x_ {0} \ in \ mathbb {R}, \; c> 0 \ quad: \ quad | f (x) | \ leq c | g (x) | \ quad \ forall x> x_ {0} \;}

{\ displaystyle \ există \; x_ {0} \ in \ mathbb {R}, \; c> 0 \ quad: \ quad | f (x) | \ leq c | g (x) | \ quad \ forall x> x_ {0} \;}

.

Notația poate fi folosită și pentru a descrie comportamentul $f$ ${\ displaystyle f}$ $f$ în vecinătatea unui număr real $la$ ${\ displaystyle a}$ $la$ : să spunem asta

f(x)\in O(g(x))

{\ displaystyle f (x) \ în O (g (x))}

{\ displaystyle f (x) \ în O (g (x))}

pentru

x\to a

{\ displaystyle x \ to a}

x \ to a

dacă și numai dacă

\exists \delta >0\;\exists c>0:|f(x)|\leq c|g(x)|

{\ displaystyle \ există \ delta> 0 \; \ există c> 0: | f (x) | \ leq c | g (x) |}

{\ displaystyle \ există \ delta> 0 \; \ există c> 0: | f (x) | \ leq c | g (x) |}

pentru

|x-a|<\delta .

{\ displaystyle | xa | <\ delta.}

{\ displaystyle | x-a | <\ delta.}

De sine $g(x)$ ${\ displaystyle g (x)}$ $g (x)$ este diferit de zero pentru valorile de $X$ ${\ displaystyle x}$ $X$ suficient de aproape de $la$ ${\ displaystyle a}$ $la$ , ambele definiții pot fi unificate folosind limita superioară :

f(x)\in O(g(x))

{\ displaystyle f (x) \ în O (g (x))}

{\ displaystyle f (x) \ în O (g (x))}

pentru

x\to a

{\ displaystyle x \ to a}

x \ to a

dacă și numai dacă

\limsup _{x\to a}\left|{\frac {f(x)}{g(x)}}\right|<\infty .

{\ displaystyle \ limsup _ {x \ to a} \ left | {\ frac {f (x)} {g (x)}} \ right | <\ infty.}

\ limsup _ {{x \ to a}} \ left | {\ frac {f (x)} {g (x)}} \ right | <\ infty.

Teoria notației O - mare: f este de ordinul g ( f ( x ) ∈ O ( g ( x ))) dacă și numai dacă există un număr real pozitiv M și un număr real x ₀ astfel încât pentru toate X , | f ( x ) | <= M ⋅ | g ( x ) |, când x < x ₀

În matematică, comportamentele asimptotice care tind spre $\infty$ ${\ displaystyle \ infty}$ $\ infty$ și a sunt luate în considerare ambele. În teoria complexității de calcul , sunt folosite doar cele care tind spre infinit; în plus, sunt considerate numai funcțiile întotdeauna pozitive, astfel încât valoarea absolută poate fi omisă.

Exemplu

Luați în considerare cele două polinoame

f(x)=6x^{4}-2x^{3}+5,

{\ displaystyle f (x) = 6x ^ {4} -2x ^ {3} +5,}

{\ displaystyle f (x) = 6x ^ {4} -2x ^ {3} +5,}

g(x)=x^{4}.

{\ displaystyle g (x) = x ^ {4}.}

{\ displaystyle g (x) = x ^ {4}.}

Atunci

f(x)\in O(g(x)){\mbox{ per }}x\rightarrow +\infty .

{\ displaystyle f (x) \ in O (g (x)) {\ mbox {per}} x \ rightarrow + \ infty.}

{\ displaystyle f (x) \ in O (g (x)) {\ mbox {per}} x \ rightarrow + \ infty.}

Demonstrație:

Arătăm asta $|f(x)|\leq C|g(x)|$ ${\ displaystyle | f (x) | \ leq C | g (x) |}$ $| f (x) | \ leq C | g (x) |$ pentru fiecare $x>1,$ ${\ displaystyle x> 1,}$ $x> 1,$ unde este $C.$ ${\ displaystyle C}$ $C.$ este o constantă pe care o vom determina mai târziu.

Presupune $x>1$ ${\ displaystyle x> 1}$ $x> 1$ . Din inegalitatea triunghiulară obținem că

|f(x)|=|6x^{4}-2x^{3}+5|\leq |6x^{4}|+|-2x^{3}|+|5|=6x^{4}+2x^{3}+5.

{\ displaystyle | f (x) | = | 6x ^ {4} -2x ^ {3} +5 | \ leq | 6x ^ {4} | + | -2x ^ {3} | + | 5 | = 6x ^ {4} + 2x ^ {3} +5.}

| f (x) | = | 6x ^ {4} -2x ^ {3} +5 | \ leq | 6x ^ {4} | + | -2x ^ {3} | + | 5 | = 6x ^ {4} + 2x ^ {3} +5.

(în ultimul pas, înlocuitorul $|-2x^{3}|=2x^{3}$ ${\ displaystyle | -2x ^ {3} | = 2x ^ {3}}$ $| -2x ^ {3} | = 2x ^ {3}$ se justifică prin faptul că $x>1>0$ ${\ displaystyle x> 1> 0}$ $x> 1> 0$ )

Observăm că pentru $x>1$ ${\ displaystyle x> 1}$ $x> 1$ inegalitățile se mențin $1<x^{3}<x^{4}$ ${\ displaystyle 1 <x ^ {3} <x ^ {4}}$ $1 <x ^ {3} <x ^ {4}$ Și $5<5x^{4}$ ${\ displaystyle 5 <5x ^ {4}}$ $5 <5x ^ {4}$ . Din acestea obținem asta

|f(x)|\leq 6x^{4}+2x^{4}+5x^{4}=13x^{4},

{\ displaystyle | f (x) | \ leq 6x ^ {4} + 2x ^ {4} + 5x ^ {4} = 13x ^ {4},}

| f (x) | \ leq 6x ^ {4} + 2x ^ {4} + 5x ^ {4} = 13x ^ {4},

prin urmare

|f(x)|\leq 13|g(x)|.

{\ displaystyle | f (x) | \ leq 13 | g (x) |.}

| f (x) | \ leq 13 | g (x) |.

Luând $C=13$ ${\ displaystyle C = 13}$ $C = 13$ obținem teza.

Probleme de notare

Declaratia " $f(x)$ ${\ displaystyle f (x)}$ $f (x)$ este de ordinul $g(x)$ ${\ displaystyle g (x)}$ $g (x)$ "este adesea scris ca" $f(x)=O(g(x))$ ${\ displaystyle f (x) = O (g (x))}$ $f (x) = O (g (x))$ Acesta este un abuz de notație : nu afirmăm cu adevărat egalitatea a două funcții, în acest sens $O(g(x))$ ${\ displaystyle O (g (x))}$ $O (g (x))$ nu reprezintă o singură funcție ci o clasă de funcții. Ar fi mai corect să scrii „ $f(x)\in O(g(x))$ ${\ displaystyle f (x) \ în O (g (x))}$ $f (x) \ în O (g (x))$ ", așa cum s-a văzut mai sus.

Uneori se scrie și " $O(f(x))=O(g(x))$ ${\ displaystyle O (f (x)) = O (g (x))}$ $O (f (x)) = O (g (x))$ „pentru a indica asta $O(f(x))\subseteq O(g(x))$ ${\ displaystyle O (f (x)) \ subseteq O (g (x))}$ $O (f (x)) \ subseteq O (g (x))$ . Și acesta este un abuz de notație: cel indicat în prima expresie nu este o adevărată egalitate, deoarece nu este simetrică. De exemplu, cu această notație avem

O(x)=O(x^{2})\quad {\mbox{ per }}x\rightarrow +\infty ,

{\ displaystyle O (x) = O (x ^ {2}) \ quad {\ mbox {per}} x \ rightarrow + \ infty,}

O (x) = O (x ^ {2}) \ quad {\ mbox {per}} x \ rightarrow + \ infty,

dar

O(x^{2})\neq O(x)\quad {\mbox{ per }}x\rightarrow +\infty ,

{\ displaystyle O (x ^ {2}) \ neq O (x) \ quad {\ mbox {per}} x \ rightarrow + \ infty,}

O (x ^ {2}) \ neq O (x) \ quad {\ mbox {per}} x \ rightarrow + \ infty,

ca funcție $f(x)=x^{2}$ ${\ displaystyle f (x) = x ^ {2}}$ $f (x) = x ^ {2}$ Și $O(x^{2})$ ${\ displaystyle O (x ^ {2})}$ $O (x ^ {2})$ dar nu $O(x)$ ${\ displaystyle O (x)}$ $O (x)$ pentru $X$ ${\ displaystyle x}$ $X$ care tinde spre infinit.

Într-o utilizare mai complexă, $O(\cdot )$ ${\ displaystyle O (\ cdot)}$ $O (\ cdot)$ poate apărea în diferite locuri într-o ecuație, chiar de mai multe ori în fiecare membru. De exemplu, următoarele afirmații sunt adevărate pentru $n\to \infty$ ${\ displaystyle n \ to \ infty}$ $n \ to \ infty$

(n+1)^{2}=n^{2}+O(n)

{\ displaystyle (n + 1) ^ {2} = n ^ {2} + O (n)}

(n + 1) ^ {2} = n ^ {2} + O (n)

(n+O(n^{1/2}))(n+O(\log \,n))^{2}=n^{3}+O(n^{5/2})

{\ displaystyle (n + O (n ^ {1/2})) (n + O (\ log \, n)) ^ {2} = n ^ {3} + O (n ^ {5/2}) }

(n + O (n ^ {{1/2}}))) (n + O (\ log \, n)) ^ {2} = n ^ {3} + O (n ^ {{5/2}} )

n^{O(1)}=O(e^{n})

{\ displaystyle n ^ {O (1)} = O (e ^ {n})}

n ^ {{O (1)}} = O (e ^ {n})

Înțelesul acestor afirmații este după cum urmează: pentru orice funcție care satisface fiecare dintre O-mare pe partea stângă, există o funcție care satisface fiecare dintre O-mare prezent pe partea dreaptă, astfel încât înlocuirea acestor funcții în ecuația face membrii egali. De exemplu, a treia ecuație înseamnă: "Pentru fiecare funcție f ( n ) ∈O (1)" există o funcție g ( n ) ∈O ( e ⁿ ) astfel încât n ^{f ( n )} = g ( n ). " În ceea ce privește mulțimile, sensul este că clasa de funcții reprezentată de membrul stâng este un subset al clasei de funcții reprezentate de membrul drept.

Ordinea funcțiilor dintre cele mai comune

Mai jos este o listă a claselor de funcții întâlnite frecvent în analiza algoritmilor. Toate acestea trebuie luate în considerare pentru $n$ ${\ displaystyle n}$ $n$ care tinde spre infinit. Funcțiile sunt enumerate prin mărire crescătoare (în termeni stabiliți, fiecare clasă de funcții enumerate este un superset al celor anterioare). În continuare, $c$ ${\ displaystyle c}$ $c$ indică o constantă arbitrară.

Notaţie	Nume	Exemplu
$O(1)$ ${\ displaystyle O (1)}$ $O (1)$	constant	Determinați dacă un număr este impar sau par
$O(\log ^{}(n))$ ${\ displaystyle O (\ log ^ {} (n))}$ $O (\ log ^ {{*}} (n))$	logaritmică iterată	Algoritmul de căutare al lui Hopcroft și Ullman pe un set disjunct (un tip de structură de date )
$O(\log(n))$ ${\ displaystyle O (\ log (n))}$ $O (\ log (n))$	logaritmic	Căutați un element dintr-o listă sortată folosind algoritmul de căutare binară
$O((\log(n))^{c})$ ${\ displaystyle O ((\ log (n)) ^ {c})}$ $O ((\ log (n)) ^ {c})$	polilogaritmică	Decideți dacă $n$ ${\ displaystyle n}$ $n$ este primul prin testul de primaritate AKS
$O(n)$ ${\ displaystyle O (n)}$ $Pe)$	liniar	Căutați un element într-o listă neordonată
$O(n\log(n))$ ${\ displaystyle O (n \ log (n))}$ $O (n \ log (n))$	logliniar	Sortați o listă după sortare heap
$O(n^{2})$ ${\ displaystyle O (n ^ {2})}$ $O (n ^ {2})$	pătratic	Sortează o listă folosind sortarea prin inserare
$O(n^{c})$ ${\ displaystyle O (n ^ {c})}$ $O (n ^ {c})$	polinom	Căutați cea mai scurtă cale pe un grafic orientat și ponderat utilizând algoritmul Floyd-Warshall
$O(c^{n})$ ${\ displaystyle O (c ^ {n})}$ $O (c ^ {n})$	exponențial , uneori numit geometric	Găsiți soluția exactă la problema vânzătorului călător (sub ipoteza că P ≠ NP )
$O(n!)$ ${\ displaystyle O (n!)}$ $Pe!)$	factorial	Orice problemă NP-completă prin intermediul unui algoritm care caută soluția cu o metodă de forță brută

Alte notații asociate

Big-O este notația asimptotică cea mai frecvent utilizată pentru compararea funcțiilor. Împreună cu alte notații înrudite formează familia notațiilor Bachmann - Landau.

O-notație mică

Intuitiv, afirmația „ $f(x)$ ${\ displaystyle f (x)}$ $f (x)$ Și $o(g(x))$ ${\ displaystyle o (g (x))}$ ${\ displaystyle o (g (x))}$ " (citit " $f(x)$ ${\ displaystyle f (x)}$ $f (x)$ este o-mic de $g(x)$ ${\ displaystyle g (x)}$ $g (x)$ ") înseamnă că $g(x)$ ${\ displaystyle g (x)}$ $g (x)$ crește mult mai repede decât $f(x).$ ${\ displaystyle f (x).}$ $f (x).$ Este $f$ ${\ displaystyle f}$ $f$ o funcție valorică reală sau complexă e $g$ ${\ displaystyle g}$ $g$ o funcție cu valoare reală, ambele definite pe un subset nelimitat de numere reale pozitive, astfel încât $g(x)$ ${\ displaystyle g (x)}$ $g (x)$ este strict pozitiv pentru toate valorile suficient de mari ale $X .$ ${\ displaystyle x.}$ ${\ displaystyle x.}$ Noi scriem

f(x)=o(g(x)),{\text{ per }}x\to \infty

{\ displaystyle f (x) = o (g (x)), {\ text {per}} x \ to \ infty}

{\ displaystyle f (x) = o (g (x)), {\ text {per}} x \ to \ infty}

dacă pentru fiecare $\varepsilon$ ${\ displaystyle \ varepsilon}$ $\ varepsilon$ adevăratul pozitiv există $Nu.$ ${\ displaystyle N}$ $Nu.$ astfel încât

$|f(x)|\leq \varepsilon g(x),\quad {\text{ per ogni }}x\geq N.$ ${\ displaystyle | f (x) | \ leq \ varepsilon g (x), \ quad {\ text {pentru fiecare}} x \ geq N.}$ ${\ displaystyle | f (x) | \ leq \ varepsilon g (x), \ quad {\ text {pentru fiecare}} x \ geq N.}$ ^[4]

De exemplu, obținem

2x=o(x^{2})

{\ displaystyle 2x = o (x ^ {2})}

{\ displaystyle 2x = o (x ^ {2})}

Și

1/x=o(1).

{\ displaystyle 1 / x = o (1).}

{\ displaystyle 1 / x = o (1).}

Diferența dintre definiția de mai sus pentru notația O mare și această definiție a micului o, este că, în timp ce prima trebuie să fie adevărată pentru cel puțin o constantă $M.,$ ${\ displaystyle M,}$ ${\ displaystyle M,}$ al doilea trebuie să fie valabil pentru fiecare constantă pozitivă $\varepsilon ,$ ${\ displaystyle \ varepsilon,}$ ${\ displaystyle \ varepsilon,}$ oricât de mică ^[5] . În acest fel, notația o-mică este „mai puternică” decât notația o-mare corespunzătoare: orice funcție care este o-mică decât $g$ ${\ displaystyle g}$ $g$ este, de asemenea, O-mare de $g,$ ${\ displaystyle g,}$ ${\ displaystyle g,}$ dar nu toate funcțiile care sunt O-mari decât $g$ ${\ displaystyle g}$ $g$ Sunt o-mic de $g .$ ${\ displaystyle g.}$ ${\ displaystyle g.}$ De exemplu, $2x^{2}=O(x^{2})$ ${\ displaystyle 2x ^ {2} = O (x ^ {2})}$ ${\ displaystyle 2x ^ {2} = O (x ^ {2})}$ dar $2x^{2}\neq o(x^{2}).$ ${\ displaystyle 2x ^ {2} \ neq sau (x ^ {2}).}$ ${\ displaystyle 2x ^ {2} \ neq sau (x ^ {2}).}$

De sine $g(x)$ ${\ displaystyle g (x)}$ $g (x)$ este diferită de zero, sau cel puțin devine diferită de la un anumit moment, relația $f(x)=o(g(x))$ ${\ displaystyle f (x) = o (g (x))}$ ${\ displaystyle f (x) = o (g (x))}$ este echivalent cu

\lim _{x\to +\infty }{\frac {f(x)}{g(x)}}=0,

{\ displaystyle \ lim _ {x \ to + \ infty} {\ frac {f (x)} {g (x)}} = 0,}

{\ displaystyle \ lim _ {x \ to + \ infty} {\ frac {f (x)} {g (x)}} = 0,}

care este modul în care Landau ^[4] a definit inițial notația o-mică.

Notarea small-o satisface următoarele proprietăți:

de sine $c$ ${\ displaystyle c}$ $c$ este o constantă diferită de zero și $f=o(g),$ ${\ displaystyle f = o (g),}$ ${\ displaystyle f = o (g),}$ asa de $c\cdot f=o(g);$ ${\ displaystyle c \ cdot f = o (g);}$ ${\ displaystyle c \ cdot f = o (g);}$

de sine $f=o(F)$ ${\ displaystyle f = o (F)}$ ${\ displaystyle f = o (F)}$ Și $g=o(G),$ ${\ displaystyle g = o (G),}$ ${\ displaystyle g = o (G),}$ asa de $f\cdot g=o(F\cdot G);$ ${\ displaystyle f \ cdot g = o (F \ cdot G);}$ ${\ displaystyle f \ cdot g = o (F \ cdot G);}$

de sine $f=o(g)$ ${\ displaystyle f = o (g)}$ ${\ displaystyle f = o (g)}$ Și $g=o(h),$ ${\ displaystyle g = o (h),}$ ${\ displaystyle g = o (h),}$ asa de $f=o(h),$ ${\ displaystyle f = o (h),}$ ${\ displaystyle f = o (h),}$ acesta este $o(o(h))=o(h).$ ${\ displaystyle o (o (h)) = o (h).}$ ${\ displaystyle o (o (h)) = o (h).}$

Notă

^ ( DE ) Bachmann Paull , Analytische Zahlentheorie , voi. 2, Leipzig, Teubner, 1894.
^ ( DE ) Edmund Landau , Handbuch der Lehre von der Verteilung der Primzahlen , Leipzig, BG Teubner, 1909, p. 883.
^ ( DE ) Edmund Landau , Handbuch der Lehre von der Verteilung der Primzahlen , Leipzig, BG Teubner, 1909, p. 31.
^ ^a ^b ( DE ) Edmund Landau , Handbuch der Lehre von der Verteilung der Primzahlen , Leipzig, BG Teubner, 1909, p. 61.
^ Thomas H. Cormen și colab., 2001, Introducere în algoritmi, ediția a doua

Elemente conexe

Estimarea asimptotică

Portal IT

Portalul de matematică

[1] ( DE ) Bachmann Paull , Analytische Zahlentheorie , voi. 2, Leipzig, Teubner, 1894.

[:0-2] ( DE ) Edmund Landau , Handbuch der Lehre von der Verteilung der Primzahlen , Leipzig, BG Teubner, 1909, p. 883.

[:2-3] ( DE ) Edmund Landau , Handbuch der Lehre von der Verteilung der Primzahlen , Leipzig, BG Teubner, 1909, p. 31.

[:4-4] ( DE ) Edmund Landau , Handbuch der Lehre von der Verteilung der Primzahlen , Leipzig, BG Teubner, 1909, p. 61.

[5] Thomas H. Cormen și colab., 2001, Introducere în algoritmi, ediția a doua

[1]

[2]

[3]

[4]

[5]

V · D · M Algoritmi de sortare
Teorie	Teoria complexității de calcul · notație Big O · Matrice · Listă · Stack · Coadă · Sortare comparativă · Sortare adaptivă
Algoritmi de schimb	Bubble sortare · Shaker sortare · par-impar sortare · Comb sortare · Gnome sortare · Quicksort
Algoritmi de selecție	Sortare selecție · Sortare grămadă · Smoothsort
Algoritmi de inserție	Inserția sortare · Shell sortare · copac sortare · Bibliotecă sortare · sortare Răbdare
Algoritmi de fuziune	Merge sort · Timsort
Algoritmi necomparativi	Sortare Radix · Sortare cupă · Sortare numărare · Sortare porumbel
Alți algoritmi	Sortarea de rețea · topologică sortare · sortare bitonic · clatite sortare
Algoritmi ineficienți	Sortare stupidă · Sortare Trippel