Lielais O apzīmējums ir spēcīgs rīks, ko izmanto datorzinātnēs, lai aprakstītu algoritmu laika vai telpas sarežģītību. Tas nodrošina standartizētu veidu, kā salīdzināt dažādu algoritmu efektivitāti, ņemot vērā to sliktākā gadījuma veiktspēju. Saprašana Lielais O apzīmējums ir būtiska, lai analizētu un izstrādātu efektīvus algoritmus.

Šajā apmācībā mēs apskatīsim pamatus Lielais O apzīmējums , tā nozīmi un to, kā analizēt algoritmu sarežģītību, izmantojot Lielais O .

Satura rādītājs

• Kas ir Big-O apzīmējums?
• Big-O apzīmējuma definīcija:
• Kāpēc lielais O apzīmējums ir svarīgs?
• Lielā O apzīmējuma īpašības
• Parastie lielo O apzīmējumi
• Kā noteikt lielo O apzīmējumu?
• Izpildlaika analīzes matemātiskie piemēri
• Izpildlaika analīzes algoritmiskie piemēri
• Algoritmu klases ar operāciju skaitu un izpildes laiku
• Lielā O apzīmējuma, lielā Ω (Omega) apzīmējuma un lielā θ (teta) apzīmējuma salīdzinājums
• Bieži uzdotie jautājumi par lielo O apzīmējumu

Kas ir Big-O apzīmējums?

Lielais-O , ko parasti dēvē par Pasūtījums no , ir veids, kā izteikt augšējā robeža algoritma laika sarežģītību, jo tas analizē sliktākajā gadījumā algoritma situācija. Tas nodrošina an augšējā robeža par laiku, ko patērē algoritms ievades lieluma izteiksmē. Tas ir apzīmēts kā O(f(n)) , kur f(n) ir funkcija, kas attēlo darbību (soļu) skaitu, ko algoritms veic, lai atrisinātu lieluma problēmu n .

Big-O apzīmējums tiek izmantots, lai aprakstītu algoritma veiktspēju vai sarežģītību. Konkrēti, tas apraksta sliktākajā gadījumā ziņā laiks vai telpas sarežģītība.

Svarīgs punkts:

• Lielais O apzīmējums apraksta tikai funkcijas asimptotisko uzvedību, nevis tās precīzu vērtību.
• The Lielais O apzīmējums var izmantot, lai salīdzinātu dažādu algoritmu vai datu struktūru efektivitāti.

Big-O apzīmējuma definīcija:

Dotas divas funkcijas f(n) un g(n) , mēs tā sakām f(n) ir O(g(n)) ja pastāv konstantes c > 0 un n ₀ >= 0 tāds f(n) <= c*g(n) visiem n>= n ₀ .

Vienkāršāk sakot, f(n) ir O(g(n)) ja f(n) aug ne ātrāk kā c*g(n) visiem n>= n₀kur c un n₀ir konstantes.

Kāpēc lielais O apzīmējums ir svarīgs?

Lielais O apzīmējums ir matemātisks apzīmējums, ko izmanto, lai aprakstītu algoritma sliktākā gadījuma laika sarežģītību vai efektivitāti vai datu struktūras sliktākā gadījuma telpas sarežģītību. Tas nodrošina veidu, kā salīdzināt dažādu algoritmu un datu struktūru veiktspēju un paredzēt, kā tie darbosies, palielinoties ievades lielumam.

Lielais O apzīmējums ir svarīgs vairāku iemeslu dēļ:

• Lielais O apzīmējums ir svarīgs, jo tas palīdz analizēt algoritmu efektivitāti.
• Tas nodrošina veidu, kā aprakstīt, kā izpildlaiks vai telpas prasības algoritms pieaugs, palielinoties ievades lielumam.
• Ļauj programmētājiem salīdzināt dažādus algoritmus un izvēlēties visefektīvāko konkrētai problēmai.
• Palīdz izprast algoritmu mērogojamību un paredzēt, kā tie darbosies, palielinoties ievades lielumam.
• Ļauj izstrādātājiem optimizēt kodu un uzlabot vispārējo veiktspēju.

Lielā O apzīmējuma īpašības:

Tālāk ir norādītas dažas svarīgas Big O apzīmējuma īpašības:

1. Refleksivitāte:

Jebkurai funkcijai f(n) f(n) = O(f(n)).

satur apakšvirkni java

Piemērs:

f(n) = n², tad f(n) = O(n²).

2. Transitivitāte:

Ja f(n) = O(g(n)) un g(n) = O(h(n)), tad f(n) = O(h(n)).

Piemērs:

f(n) = n³, g(n) = n², h(n) = n⁴. Tad f(n) = O(g(n)) un g(n) = O(h(n)). Tāpēc f(n) = O(h(n)).

3. Pastāvīgais faktors:

Jebkurai konstantei c> 0 un funkcijām f(n) un g(n), ja f(n) = O(g(n)), tad cf(n) = O(g(n)).

Piemērs:

f(n) = n, g(n) = n². Tad f(n) = O(g(n)). Tāpēc 2f(n) = O(g(n)).

4. Summas noteikums:

Ja f(n) = O(g(n)) un h(n) = O(g(n)), tad f(n) + h(n) = O(g(n)).

Piemērs:

f(n) = n², g(n) = n³, h(n) = n⁴. Tad f(n) = O(g(n)) un h(n) = O(g(n)). Tāpēc f(n) + h(n) = O(g(n)).

5. Produkta noteikums:

Ja f(n) = O(g(n)) un h(n) = O(k(n)), tad f(n) * h(n) = O(g(n) * k(n)) .

Piemērs:

f(n) = n, g(n) = n², h(n) = n³, k(n) = n⁴. Tad f(n) = O(g(n)) un h(n) = O(k(n)). Tāpēc f(n) * h(n) = O(g(n) * k(n)) = O(n)⁵).

6. Sastāva noteikums:

Ja f(n) = O(g(n)) un g(n) = O(h(n)), tad f(g(n)) = O(h(n)).

Piemērs:

f(n) = n², g(n) = n, h(n) = n³. Tad f(n) = O(g(n)) un g(n) = O(h(n)). Tāpēc f(g(n)) = O(h(n)) = O(n³).

Parastie lielo O apzīmējumi:

Big-O apzīmējums ir veids, kā izmērīt algoritma laika un telpas sarežģītību. Tas apraksta sarežģītības augšējo robežu sliktākajā gadījumā. Apskatīsim dažādus laika sarežģītības veidus:

1. Lineārā laika sarežģītība: liela O(n) sarežģītība

Lineārā laika sarežģītība nozīmē, ka algoritma darbības laiks pieaug lineāri līdz ar ievades lielumu.

Piemēram, apsveriet algoritmu, kas šķērso masīvu, lai atrastu konkrētu elementu :

bool findElement(int arr[], int n, int key) {  for (int i = 0; i < n; i++) {  if (arr[i] == key) {  return true;  }  }  return false; }>

2. Logaritmiskā laika sarežģītība: liela O(log n) sarežģītība

Logaritmiskā laika sarežģītība nozīmē, ka algoritma darbības laiks ir proporcionāls ievades lieluma logaritmam.

Piemēram, a binārās meklēšanas algoritms ir logaritmiska laika sarežģītība:

int binarySearch(int arr[], int l, int r, int x) {  if (r>= l) { int mid = l + (r - l) / 2;  if (arr[mid] == x) return mid;  if (arr[mid]> x) return binarySearch(arr, l, mid - 1, x);  return binarySearch(arr, mid + 1, r, x);  } atgriešanās -1; }>

3. Kvadrātiskā laika sarežģītība: liels O(n²) Sarežģītība

Kvadrātiskā laika sarežģītība nozīmē, ka algoritma darbības laiks ir proporcionāls ievades lieluma kvadrātam.

Piemēram, vienkāršs burbuļu kārtošanas algoritms ir kvadrātiskā laika sarežģītība:

void bubbleSort(int arr[], int n) {  for (int i = 0; i < n - 1; i++) {  for (int j = 0; j < n - i - 1; j++) {  if (arr[j]>arr[j + 1]) { mijmaiņas (&arr[j], &arr[j + 1]);  } } } }>

4. Kubiskā laika sarežģītība: liels O(n³) Sarežģītība

Kubiskā laika sarežģītība nozīmē, ka algoritma darbības laiks ir proporcionāls ievades lieluma kubam.

Piemēram, naivs matricas reizināšanas algoritms ir kubiskā laika sarežģītība:

void multiply(int mat1[][N], int mat2[][N], int res[][N]) {  for (int i = 0; i < N; i++) {  for (int j = 0; j < N; j++) {  res[i][j] = 0;  for (int k = 0; k < N; k++)  res[i][j] += mat1[i][k] * mat2[k][j];  }  } }>

5. Polinoma laika sarežģītība: liels O(n^k) Sarežģītība

Polinoma laika sarežģītība attiecas uz algoritma laika sarežģītību, ko var izteikt kā ievades lieluma polinoma funkciju n . Lielajā O Apzīmējums, algoritmam ir polinoma laika sarežģītība, ja tā laika sarežģītība ir tāda O(n ^k ) , kur k ir konstante un apzīmē polinoma pakāpi.

Algoritmi ar polinoma laika sarežģītību parasti tiek uzskatīti par efektīviem, jo ​​darbības laiks pieaug saprātīgā ātrumā, palielinoties ievades lielumam. Parastie algoritmu piemēri ar polinoma laika sarežģītību ietver lineārā laika sarežģītība O(n) , kvadrātiskā laika sarežģītība O(n ² ) , un kubiskā laika sarežģītība O(n ³ ) .

6. Eksponenciālā laika sarežģītība: liela O(2ⁿ) Sarežģītība

Eksponenciālā laika sarežģītība nozīmē, ka algoritma darbības laiks dubultojas ar katru pievienošanu ievades datu kopai.

Piemēram, problēma ģenerējot visas kopas apakškopas ir eksponenciālas laika sarežģītības pakāpe:

void generateSubsets(int arr[], int n) {  for (int i = 0; i < (1 << n); i++) {  for (int j = 0; j < n; j++) {  if (i & (1 << j)) {  cout << arr[j] << ' ';  }  }  cout << endl;  } }>

Faktoriāla laika sarežģītība: liela O(n!) sarežģītība

Faktoriālā laika sarežģītība nozīmē, ka algoritma darbības laiks palielinās atkarībā no ievades lieluma. To bieži var redzēt algoritmos, kas ģenerē visas datu kopas permutācijas.

Šis ir faktoriālā laika sarežģītības algoritma piemērs, kas ģenerē visas masīva permutācijas:

void permute(int* a, int l, int r) {  if (l == r) {  for (int i = 0; i <= r; i++) {  cout << a[i] << ' ';  }  cout << endl;  }  else {  for (int i = l; i <= r; i++) {  swap(a[l], a[i]);  permute(a, l + 1, r);  swap(a[l], a[i]); // backtrack  }  } }>

Ja mēs attēlosim visbiežāk sastopamos Big O apzīmējumu piemērus, mēs iegūtu šādu grafiku:

Kā noteikt lielo O apzīmējumu?

Lielais O apzīmējums ir matemātisks apzīmējums, ko izmanto, lai aprakstītu asimptotiska uzvedība funkcijas, jo tās ievade kļūst bezgalīgi liela. Tas nodrošina veidu, kā raksturot algoritmu un datu struktūru efektivitāti.

Darbības, lai noteiktu lielo O apzīmējumu:

1. Identificējiet dominējošo terminu:

• Izpētiet funkciju un identificējiet terminu ar visaugstāko pieauguma pakāpi, palielinoties ievades lielumam.
• Ignorējiet visus nemainīgos faktorus vai zemākas kārtas vārdus.

2. Nosakiet izaugsmes secību:

• Dominējošā vārda pieauguma secība nosaka Big O apzīmējumu.

3. Uzrakstiet lielo O apzīmējumu:

• Lielo O apzīmējumu raksta kā O(f(n)), kur f(n) apzīmē dominējošo vārdu.
• Piemēram, ja dominējošais vārds ir n^2, lielais O apzīmējums būtu O(n^2).

4. Vienkāršojiet apzīmējumu (neobligāti):

• Dažos gadījumos, Big O zīmols n var vienkāršot, noņemot nemainīgos faktorus vai izmantojot kodolīgāku apzīmējumu.
• Piemēram, O(2n) var vienkāršot līdz O(n).

Piemērs:

Funkcija: f(n) = 3n³+ 2n²+ 5n + 1

1. Dominējošais termins: 3n³
2. Izaugsmes secība: kubiskais (n³)
3. Lielais O apzīmējums: O (n³)
4. Vienkāršots apzīmējums: O(n³)

Izpildlaika analīzes matemātiskie piemēri:

Zemāk redzamā tabula ilustrē dažādu algoritmu secību izpildlaika analīzi, palielinoties ievades lielumam (n).

Izpildlaika analīzes algoritmiskie piemēri:

Zemāk esošajā tabulā ir klasificēti algoritmi, pamatojoties uz to izpildlaika sarežģītību, un sniegti piemēri katram veidam.

Algoritmu klases ar operāciju skaitu un izpildes laiku:

Tālāk ir norādītas algoritmu klases un to izpildes laiki datorā, kas tiek izpildīts 1 miljons darbību sekundē (1 s = 10 ⁶ μs = 10 ³ msec) :

Lielā O apzīmējuma, lielā Ω (Omega) apzīmējuma un lielā θ (teta) apzīmējuma salīdzinājums:

Tālāk ir sniegta tabula, kurā salīdzināts Big O apzīmējums, Ω (Omega) un θ (Theta) apzīmējums:

Katrā apzīmējumā:

• f(n) apzīmē analizējamo funkciju, parasti algoritma laika sarežģītību.
• g(n) apzīmē noteiktu funkciju, kas ierobežo f(n) .
• C, C1, un C2 ir konstantes.
• n ₀ ir minimālais ievades lielums, pēc kura pastāv nevienlīdzība.

Šie apzīmējumi tiek izmantoti, lai analizētu algoritmus, pamatojoties uz tiem sliktākais gadījums (Big O) , labākais gadījums (Ω) , un vidējais gadījums (θ) scenāriji.

Bieži uzdotie jautājumi par lielo O apzīmējumu:

1. jautājums. Kas ir lielais O apzīmējums?

Atbilde: Lielais O apzīmējums ir matemātisks apzīmējums, ko izmanto, lai aprakstītu algoritma laika sarežģītības augšējo robežu, ņemot vērā to, kā tas pieaug attiecībā pret ievades lielumu.

2. jautājums. Kāpēc lielais O apzīmējums ir svarīgs?

Atbilde: Tas palīdz mums analizēt un salīdzināt algoritmu efektivitāti, koncentrējoties uz sliktāko scenāriju un izprotot, kā to veiktspēja mainās atkarībā no ievades lieluma.

3. jautājums. Kā tiek aprēķināts lielais O apzīmējums?

Atbilde: Lielo O apzīmējumu nosaka, identificējot dominējošo darbību algoritmā un izsakot tās laika sarežģītību n izteiksmē, kur n apzīmē ievades lielumu.

4. jautājums. Ko O(1) nozīmē lielajā O apzīmējumā?

Atbilde: O (1) apzīmē pastāvīgu laika sarežģītību, norādot, ka algoritma izpildes laiks nemainās neatkarīgi no ievades lieluma.

5. jautājums. Kāda ir dažādu lielo O sarežģītību, piemēram, O(log n) vai O(n^2) nozīme?

Atbilde: Dažādas sarežģītības, piemēram, O(log n) vai O(n^2), atspoguļo algoritma veiktspējas mērogošanu, palielinoties ievades lielumam, sniedzot ieskatu tā efektivitātē un mērogojamībā.

6. jautājums. Vai lielo O apzīmējumu var attiecināt arī uz telpas sarežģītību?

Atbilde: Jā, Big O notation var izmantot arī, lai analizētu un aprakstītu algoritma telpas sarežģītību, norādot, cik daudz atmiņas tam nepieciešams attiecībā pret ievades lielumu.

Saistīts raksts:

• Big-O analīzes piemēri
• Algoritmu projektēšana un analīze
• Asimptotisko apzīmējumu veidi algoritmu sarežģītības analīzē
• Algoritmu analīze | Liels – Ω (Big- Omega) Apzīmējums
• Algoritmu analīze | mazie o un mazie omega apzīmējumi