Big O notācija

Big O notācija ir algoritmu salīdzināšanas veids. Tā tos salīdzina, aprēķinot, cik daudz atmiņas ir nepieciešams un cik daudz laika ir nepieciešams, lai to izpildītu.

Lielo O apzīmējumu bieži izmanto, lai noteiktu, cik sarežģīta ir problēma, ko dēvē arī par problēmas sarežģītības klasi. Matemātiķis Pauls Bachmans (1837-1920) bija pirmais, kurš 1896. gadā izmantoja šo apzīmējumu savas grāmatas "Analytische Zahlentheorie" otrajā izdevumā. Edmunds Landau (1877-1938) šo apzīmējumu popularizēja. Tāpēc, runājot par Landau simboliem, cilvēki atsaucas uz šo pierakstu.

Lielais O apzīmējums ir nosaukts pēc termina "funkcijas kārtība", kas attiecas uz funkciju augšanu. Lielo O notāciju izmanto, lai atrastu funkcijas augšanas ātruma augšējo robežu (augstāko iespējamo lielumu), tas nozīmē, ka tā nosaka ilgāko laiku, kas būs nepieciešams, lai ievades datus pārvērstu izejas datos. Tas nozīmē, ka algoritmu var sagrupēt pēc tā, cik ilgi tas var aizņemt sliktākajā gadījumā, kad katru reizi tiks izvēlēts garākais ceļš.

Big O ir izteiksme, kas nosaka sliktākā scenārija izpildes laiku, parādot, cik efektīvs ir algoritms, neizpildot programmu datorā. Tas ir noderīgi arī tāpēc, ka dažādiem datoriem var būt atšķirīga aparatūra, un tāpēc tās izpildei var būt nepieciešams atšķirīgs laiks. Tā kā Big O vienmēr pieņem visnelabvēlīgāko scenāriju, tas var parādīt konsekventu ātruma mērījumu: neatkarīgi no jūsu aparatūras O ( 1 ) {\displaystyle O(1)} $O(1)$ vienmēr tiks pabeigts ātrāk nekā O ( n ! ) {\displaystyle O(n!)}, $O(n!)$ jo tiem ir dažādi efektivitātes līmeņi.

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ā.