Kas ir Big O notācija? Algoritmu laika un atmiņas sarežģītība

Big O notācija ir algoritmu salīdzināšanas veids. Tā apraksta, kā algoritma izpildes laiks vai nepieciešamā atmiņa aug, palielinoties ievades datu apjomam. Big O parasti nosaka algoritma asimptotisko augšējo robežu — cik daudz resursu algoritms var prasīt sliktākajā gadījumā.

Kas tiek mērīts: laiks un atmiņa

Ar Big O var mērīt gan laika sarežģītību (cik daudz operāciju vai laika soļu nepieciešams), gan atmiņas sarežģītību (cik papildu atmiņas vietas algoritms izmanto). Laika sarežģītība parasti izsaka, kā izpildes laiks aug attiecībā pret ievades lielumu n, savukārt atmiņas sarežģītība — cik daudz papildus atmiņas (piem., masīvu, sarakstu) algoritms pieprasa.

Bieži sastopamās notācijas un piemēri

O(1) — konstanta laika: izpildes laiks nemainās, palielinoties n (piem., piekļuve masīva elementam pēc indeksa). O ( 1 ) {\displaystyle O(1)} $O(1)$
O(log n) — logaritmiska: piemēram, binārā meklēšana sakārtotā sarakstā.
O(n) — lineāra: algoritma darbības skaits proporcionāls ievades lielumam (piem., vienkārša skenēšana cauri sarakstam).
O(n log n) — efekti īstermiņā, piemēram, daudzas sadalīšanas un apvienošanas šķirošanas metodes (merge sort, heapsort).
O(n^2) — kvadrātiska: bieži parādās divkāršās cilpas (piem., vienkārša izvēles šķirošana vai burtveidīgs salīdzinājums pāros).
O(2^n) un O(n!) — eksponenciālas un faktoriālas: paraugpiemēri no kombinatorikas un izsmeļošu meklēšanas risinājumiem. O ( n ! ) {\displaystyle O(n!)}, $O(n!)$

Sliktākais, labākais un vidējais gadījums

Big O parasti apraksta sliktāko gadījumu (worst-case). Pastāv arī citas notācijas:

Ω (Big Omega) — apakšējā robeža (best-case).
Θ (Big Theta) — asimptotiska precīza robeža (augšējā un apakšējā robeža vienādas).

Piemēram, kārtošanas algoritmam QuickSort vidējā sarežģītība ir O(n log n), bet sliktākajā gadījumā — O(n^2), ja tiek izvēlēts neveiksmīgs pivot.

Kā aprēķina Big O — pamatprincipi

Definē mainīgo n kā ievades lielumu (elementu skaits, bitu skaits u. tml.).
Skaita pamatoperācijas atkarībā no n (cilpas, rekursijas izsaukumi, salīdzinājumi).
Noņem konstantu koeficientus (piem., 2n → O(n)).
Atmet zemākas pakāpes locekļus, kad n → ∞ (piem., n^2 + n → O(n^2)).

Ja ir vairāki secīgi posmi, ņem lielāko rangu (piem., ja viens posms ir O(n) un nākamais O(n^2), kopējais ir O(n^2)). Ja posmi izpildās paralēli (vai tiek izvēlēts viens no tiem), tad izmanto minimālo vai atbilstošo kombināciju atkarībā no konteksta.

Vienkārši kodu piemēri

1) Viena cilpa: for (i = 0; i < n; i++) → O(n).
2) Dubulta cilpa: for (i = 0; i < n; i++) { for (j = 0; j < n; j++) { … } } → O(n^2).
3) Rekursīva dalīšana uz pusēm: T(n) = T(n/2) + O(1) → O(log n) (piem., binārā meklēšana).

Praktiski apsvērumi

Big O ignorē konstantu faktoru un zemākas pakāpes, tāpēc tas ir labs rīks, lai salīdzinātu algoritmu mērogojamību, bet ne vienmēr parāda reālo izpildes laiku mazam vai vidējam n. Konkrētā aparatūra, atmiņas piekļuves kavēšanās (cache), paralēlisms un implementācijas detaļas var būt būtiski. Tāpēc inženieri bieži ņem vērā arī laika komplekta mērījumus un praktisku profilēšanu.

Vēsture

Lielo O apzīmējumu 1896. gadā savas grāmatas "Analytische Zahlentheorie" otrajā izdevumā pirmo reizi izmantoja Pauls Bachmanns (1837–1920). To popularizēja Edmunds Landau (1877–1938), un tāpēc šo pierakstu mēdz saukt arī par Landau simboliem.

Secinājums

Big O notācija ir būtisks instruments datu struktūru un algoritmu analīzē — tā ļauj novērtēt, kā algoritms mērogojas, salīdzināt atšķirīgas pieejas un izprast robežas, kas saistītas ar laiku un atmiņu. Lai pieņemtu praktiskus lēmumus, to vislabāk kombinēt ar reāliem mērījumiem un domāšanu par konkrēto problēmu un aparatūru.

Piemēri

Visos turpmākajos piemēros ir izmantots Python rakstīts kods. Ņemiet vērā, ka šis nav pilnīgs Big O tipu saraksts.

Pastāvīgs

O ( 1 ) {\displaystyle O(1)} $O(1)$ . Vienmēr aizņem tikpat daudz laika neatkarīgi no ievades. Piemēram, ņemiet funkciju, kas pieņem veselu skaitli (saukts par x) un atgriež divkāršu tā vērtību:

def double(x): return x * 2 #Atgriež x vērtību, reizinātu ar 2

Pēc ievades saņemšanas šī funkcija vienmēr veiks vienu soli, lai atgrieztu izvades rezultātu. Tā ir konstanta, jo vienmēr aizņems vienu un to pašu laiku, tātad tā ir O ( 1 ) {\displaystyle O(1)} $O(1)$ .

Lineārais

O ( n ) {\displaystyle O(n)} $O(n)$ . Palielinās atkarībā no ievades lieluma, ko pārstāv n {\displaystyle n} . Pieņemsim, ka funkcija pieņem n un atgriež katru skaitli no 1 līdz n:

def count(n): i = 1 #Izveido skaitītāju "i" ar vērtību 1 while i <= n: #Komentā i ir mazāks vai vienāds ar n print(i) #Izdrukāt i vērtību i = i + 1 #Noteikt i kā "vērtība i + 1".

Ja mēs ievadītu vērtību 5, tad tiktu izvadīta 1 , 2 , 3 , 4 , 5 {\displaystyle 1,2,2,3,4,5}. $1,2,3,4,5$ , lai pabeigtu 5 cilpas. Līdzīgi, ja mēs ievadītu 100, tad tas izvadītu 1 , 2 , 3...98 , 99 , 100 {\displaystyle 1,2,3...98,99,100} $1,2,3...98,99,100$ , un tam būtu jāveic 100 cilpas. Ja ievade ir n {\displaystyle n}, tad algoritma izpildes laiks katru reizi ir tieši n {\displaystyle n} cilpu, tāpēc tas ir O ( n ) {\displaystyle O(n)} $O(n)$ .

Faktoriālais

O ( n ! ) {\displaystyle O(n!)} $O(n!)$ . Palielinās faktoriāli, kas nozīmē, ka nepieciešamais laiks masveidā palielinās līdz ar ievades apjomu. Piemēram, pieņemsim, ka mēs vēlamies apmeklēt piecas pilsētas visā pasaulē un vēlamies redzēt visus iespējamos sakārtojumus (permutācijas). Algoritms, ko mēs varētu uzrakstīt, izmantojot Python itertools bibliotēku, ir šāds:

import itertools #Importēt itertools bibliotēku cities = ['London', 'Paris', 'Berlin', 'Amsterdam', 'Rome'] #Mūsu izvēlēto pilsētu masīvs def permutations(cities): pilsētu masīva ievadīšana: for i in itertools. permutations(cities): #Par katru mūsu elementu permutāciju (kas piešķirta mainīgajam "i") print(i) #Izejas i

Šis algoritms aprēķinās katru mūsu pilsētu unikālo permutāciju un pēc tam to izvadīs. Izvades piemēri būs šādi:

("Londona", "Parīze", "Berlīne", "Amsterdama", "Roma") ("Londona", "Parīze", "Berlīne", "Roma", "Amsterdama") ("Londona", "Parīze", "Amsterdama", "Berlīne", "Roma") ... ("Roma", "Amsterdama", "Parīze", "Berlīne", "Londona") ("Roma", "Amsterdama", "Berlīne", "Londona", "Parīze") ("Roma", "Amsterdama", "Berlīne", "Parīze", "Londona").

Šajā gadījumā mūsu ievades saraksts ir 5 elementi, un ar katru izvēli atlikušās iespējas samazinās par 1. Citiem vārdiem sakot, mūsu 5 ievades elementi izvēlas 5 × 4 × 3 × 2 × 1 {\displaystyle 5\reiz 4\reiz 3\reiz 2\reiz 1} $5\times 4\times 3\times 2\times 1$ elementus (vai 5 ! {\displaystyle 5!} $5!$ ). Ja mūsu ieejas dati ir n {\displaystyle n} pilsētu gari, tad izejas datu skaits ir n ! {\displaystyle n! } $n!$ ; citiem vārdiem sakot, pieņemot, ka mēs izstaigājam katru permutāciju, mums būs nepieciešams O ( n ! ) {\displaystyle O(n!)} $O(n!)$ ciklu, lai to pabeigtu.

Little-o notācija

Lielā O stingrāka versija ir little-o. Atšķirība starp lielo O un little-o ir tāda, ka little-o ir stingra augšējā robeža: kamēr O ( n ) {\displaystyle O(n)} $O(n)$ nozīmē, ka pabeigšanas laiks palielināsies līdz šim maksimumam, pamatojoties uz ievades lielumu, o ( n ) {\displaystyle o(n)} nozīmē, ka $o(n)$ pabeigšanas laiks parasti būs mazāks par šo laika daudzumu. Citiem vārdiem sakot, Big O pieņem, ka katra cilpa iet pa visgarāko ceļu un process ilgs pēc iespējas ilgāk, savukārt little-o ir reālistiskāks attiecībā uz faktisko izpildes laiku; ja cilpu skaits ir balstīts uz sešstūra kauliņa mešanu, Big O vienmēr pieņems, ka tiek mests 6, bet little-o ņems vērā vienādu citu skaitļu mešanas varbūtību.

Jautājumi un atbildes

J: Kas ir Big O notācija?

A: Big O notācija ir veids, kā salīdzināt dažādu funkciju pieauguma tempus, ko bieži izmanto, lai salīdzinātu dažādu algoritmu efektivitāti, aprēķinot, cik daudz atmiņas un laika nepieciešams, lai to izpildītu. To var izmantot arī, lai noteiktu, cik sarežģīta ir problēma.

J: Kurš pirmais izmantoja šo apzīmējumu?

A: Matemātiķis Pauls Bachmans (Paul Bachmann, 1837-1920) bija pirmais, kurš 1896. gadā savā grāmatā "Analytische Zahlentheorie" izmantoja šo pierakstu.

J: Ko apzīmē lielais O?

A: "Big O" ir apzīmējums "funkcijas kārtībai", kas attiecas uz funkciju pieauguma ātrumu.

J: Kā izmanto lielo O?

A: Big O apzīmējumu izmanto, lai atrastu funkcijas augšanas ātruma augšējo robežu (augstāko iespējamo lielumu), t. i., lai noteiktu ilgāko laiku, kas būs nepieciešams, lai ieejas datus pārvērstu izejas datos. Tas nozīmē, ka algoritmus var sagrupēt pēc tā, cik ilgs laiks tiem nepieciešams sliktākajā gadījumā, kad katru reizi tiks izvēlēts garākais ceļš.

J: Kas ir Landau simboli?

A: Landau simboli attiecas uz Big O notāciju, kas nosaukta Edmunda Landau (1877-1938) vārdā, kurš šo notāciju popularizēja.

J: Kāpēc Big O ir noderīgs?

A:Big O ļauj izmērīt ātrumu, neizmantojot programmas datoros, jo tajā vienmēr tiek pieņemts vissliktākais scenārijs, tādējādi tas ir konsekvents neatkarīgi no datoru aparatūras atšķirībām. Tas arī parāda, cik efektīvs ir algoritms, neprasot to reāli palaist datorā.