Iso O-merkintä on tehokas työkalu, jota käytetään tietojenkäsittelytieteessä kuvaamaan algoritmien aika- tai tilamonimutkaisuutta. Se tarjoaa standardoidun tavan verrata eri algoritmien tehokkuutta niiden pahimman mahdollisen suorituskyvyn suhteen. Ymmärtäminen Iso O-merkintä on välttämätöntä tehokkaiden algoritmien analysoinnissa ja suunnittelussa.

Tässä opetusohjelmassa käsittelemme perusasiat Iso O-merkintä , sen merkitys ja kuinka analysoida algoritmien monimutkaisuutta käyttämällä Iso O .

Sisällysluettelo

• Mikä on Big-O-merkintä?
• Big-O-merkinnän määritelmä:
• Miksi Big O -merkintä on tärkeä?
• Big O -merkinnän ominaisuudet
• Yleiset Big-O-merkinnät
• Kuinka määrittää suuri O-merkintä?
• Matemaattisia esimerkkejä ajonaikaisesta analyysistä
• Algoritmiset esimerkit ajonaikaisesta analyysistä
• Algoritmiluokat operaatioiden lukumäärällä ja suoritusajalla
• Big O -merkinnän, Big Ω (Omega) -merkinnän ja Big θ (theta) -merkinnän vertailu
• Usein kysyttyjä kysymyksiä Big O Notationista

Mikä on Big-O-merkintä?

Iso-O , jota kutsutaan yleisesti nimellä Järjestys , on tapa ilmaista yläraja algoritmin aikamonimutkaisuudesta, koska se analysoi Pahimmassa tapauksessa algoritmin tilanne. Se tarjoaa an yläraja algoritmin käyttämä aika tulon koon mukaan. Se on merkitty nimellä O(f(n)) , missä f(n) on funktio, joka edustaa operaatioiden (askeleiden) määrää, jonka algoritmi suorittaa ratkaistakseen kokoongelman n .

Big-O-merkintä käytetään kuvaamaan algoritmin suorituskykyä tai monimutkaisuutta. Tarkemmin sanottuna se kuvaa pahimmassa tapauksessa suhteen aika tai tilan monimutkaisuus.

Tärkeä pointti:

• Iso O-merkintä kuvaa vain funktion asymptoottista käyttäytymistä, ei sen tarkkaa arvoa.
• The Iso O-merkintä voidaan verrata eri algoritmien tai tietorakenteiden tehokkuutta.

Big-O-merkinnän määritelmä:

Annettu kaksi toimintoa f(n) ja g(n) , sanomme niin f(n) On O(g(n)) jos on olemassa vakioita c> 0 ja n ₀ >= 0 sellaista f(n) <= c*g(n) kaikille n>= n ₀ .

Yksinkertaisemmin sanottuna f(n) On O(g(n)) jos f(n) ei kasva nopeammin kuin c*g(n) kaikille n>= n₀missä c ja n₀ovat vakioita.

Miksi Big O -merkintä on tärkeä?

Big O -merkintä on matemaattinen merkintä, jota käytetään kuvaamaan algoritmin pahimman tapauksen aikamonimutkaisuutta tai tehokkuutta tai tietorakenteen pahimman tapauksen avaruuden monimutkaisuutta. Se tarjoaa tavan verrata eri algoritmien ja tietorakenteiden suorituskykyä ja ennustaa, kuinka ne käyttäytyvät syötteen koon kasvaessa.

Iso O-merkintä on tärkeä useista syistä:

• Big O Notation on tärkeä, koska se auttaa analysoimaan algoritmien tehokkuutta.
• Se tarjoaa tavan kuvata, kuinka suoritusaika tai tilavaatimukset algoritmi kasvaa syötteen koon kasvaessa.
• Antaa ohjelmoijille mahdollisuuden verrata erilaisia ​​algoritmeja ja valita tehokkain tiettyyn ongelmaan.
• Auttaa ymmärtämään algoritmien skaalautuvuutta ja ennustamaan, kuinka ne toimivat syötteen koon kasvaessa.
• Antaa kehittäjille mahdollisuuden optimoida koodia ja parantaa yleistä suorituskykyä.

Big O -merkinnän ominaisuudet:

Alla on joitain tärkeitä Big O -merkinnän ominaisuuksia:

arraylist lajitella

1. Heijastuskyky:

Mille tahansa funktiolle f(n), f(n) = O(f(n)).

Esimerkki:

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

2. Transitiivisuus:

Jos f(n) = O(g(n)) ja g(n) = O(h(n)), niin f(n) = O(h(n)).

Esimerkki:

f(n) = n³, g(n) = n², h(n) = n⁴. Sitten f(n) = O(g(n)) ja g(n) = O(h(n)). Siksi f(n) = O(h(n)).

3. Vakiokerroin:

Jokaiselle vakiolle c> 0 ja funktioille f(n) ja g(n), jos f(n) = O(g(n)), niin cf(n) = O(g(n)).

Esimerkki:

f(n) = n, g(n) = n². Silloin f(n) = O(g(n)). Siksi 2f(n) = O(g(n)).

4. Summa-sääntö:

Jos f(n) = O(g(n)) ja h(n) = O(g(n)), niin f(n) + h(n) = O(g(n)).

Esimerkki:

f(n) = n², g(n) = n³, h(n) = n⁴. Sitten f(n) = O(g(n)) ja h(n) = O(g(n)). Siksi f(n) + h(n) = O(g(n)).

5. Tuotesääntö:

Jos f(n) = O(g(n)) ja h(n) = O(k(n)), niin f(n) * h(n) = O(g(n) * k(n)) .

Esimerkki:

f(n) = n, g(n) = n², h(n) = n³, k(n) = n⁴. Sitten f(n) = O(g(n)) ja h(n) = O(k(n)). Siksi f(n) * h(n) = O(g(n) * k(n)) = O(n)⁵).

6. Koostumussääntö:

Jos f(n) = O(g(n)) ja g(n) = O(h(n)), niin f(g(n)) = O(h(n)).

Esimerkki:

f(n) = n², g(n) = n, h(n) = n³. Sitten f(n) = O(g(n)) ja g(n) = O(h(n)). Siksi f(g(n)) = O(h(n)) = O(n³).

Yleiset Big-O-merkinnät:

Big-O-merkintä on tapa mitata algoritmin aika- ja tilamonimutkaisuutta. Se kuvaa monimutkaisuuden ylärajaa pahimmassa tapauksessa. Tarkastellaan erityyppisiä aikamonimutkauksia:

1. Lineaarinen aikamonimutkaisuus: Big O(n) -monimutkaisuus

Lineaarinen aikamonimutkaisuus tarkoittaa, että algoritmin käyntiaika kasvaa lineaarisesti syötteen koon mukaan.

Harkitse esimerkiksi algoritmia, joka kulkee taulukon läpi löytääkseen tietyn elementin :

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

2. Logaritminen aikamonimutkaisuus: Big O(log n) -monimutkaisuus

Logaritminen aikakompleksisuus tarkoittaa, että algoritmin ajoaika on verrannollinen syötteen koon logaritmiin.

Esimerkiksi a binäärihakualgoritmi on logaritminen aikamonimutkaisuus:

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);  } paluu -1; }>

3. Kvadraattisen ajan monimutkaisuus: Big O(n²) Monimutkaisuus

Neliöllinen aikamonimutkaisuus tarkoittaa, että algoritmin ajoaika on verrannollinen syötteen koon neliöön.

Esimerkiksi yksinkertainen kuplalajittelualgoritmi sillä on neliöllinen aikamonimutkaisuus:

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]) { swap(&arr[j], &arr[j + 1]);  } } } }>

4. Kuutioajan monimutkaisuus: Big O(n³) Monimutkaisuus

Kuutioaikainen monimutkaisuus tarkoittaa, että algoritmin ajoaika on verrannollinen syötteen koon kuutioon.

Esimerkiksi naivi matriisin kertolaskualgoritmi sillä on kuutioaikainen monimutkaisuus:

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. Polynomiajan monimutkaisuus: Big O(n^k) Monimutkaisuus

Polynominen aikakompleksisuudella tarkoitetaan algoritmin aikamonimutkaisuutta, joka voidaan ilmaista syötteen koon polynomifunktiona n . Isossa O merkintätapa, algoritmilla sanotaan olevan polynominen aikamonimutkaisuus, jos sen aikamonimutkaisuus on Päällä ^k ) , missä k on vakio ja edustaa polynomin astetta.

Algoritmeja, joiden aika monimutkaisuus on polynomi, pidetään yleensä tehokkaina, koska ajoaika kasvaa kohtuullista vauhtia syötteen koon kasvaessa. Yleisiä esimerkkejä algoritmeista, joiden aika monimutkaisuus on polynomi, ovat mm lineaarinen aikakompleksi O(n) , neliöllinen aikakompleksi O(n ² ) , ja kuutioaika monimutkaisuus O(n ³ ) .

6. Eksponentiaalinen aikamonimutkaisuus: Big O(2ⁿ) Monimutkaisuus

Eksponentiaalinen aikamonimutkaisuus tarkoittaa, että algoritmin ajoaika kaksinkertaistuu jokaisen lisäyksen yhteydessä syöttötietosarjaan.

Esimerkiksi ongelma luomalla joukon kaikki osajoukot on eksponentiaalisesti monimutkainen:

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;  } }>

Faktoriaalinen ajan monimutkaisuus: Suuri O(n!) Monimutkaisuus

Faktoriaalinen aikamonimutkaisuus tarkoittaa, että algoritmin ajoaika kasvaa tekijällisesti syötteen koon mukaan. Tämä näkyy usein algoritmeissa, jotka luovat kaikki tietojoukon permutaatiot.

Tässä on esimerkki tekijän aikakompleksisuuden algoritmista, joka luo kaikki taulukon permutaatiot:

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  }  } }>

Jos piirrämme yleisimmät Big O -merkintäesimerkit, saamme seuraavanlaisen kaavion:

Kuinka määrittää suuri O-merkintä?

Iso O-merkintä on matemaattinen merkintä, jota käytetään kuvaamaan asymptoottinen käyttäytyminen funktiosta, kun sen syöte kasvaa äärettömän suureksi. Se tarjoaa tavan karakterisoida algoritmien ja tietorakenteiden tehokkuutta.

Vaiheet suuren O-merkinnän määrittämiseksi:

1. Tunnista hallitseva termi:

• Tutki funktiota ja tunnista termi, jonka kasvu on suurinta syötteen koon kasvaessa.
• Ohita kaikki vakiotekijät tai alemman kertaluvun termit.

2. Määritä kasvujärjestys:

• Dominoivan termin kasvujärjestys määrittää Big O -merkinnän.

3. Kirjoita iso O-merkintä:

• Big O -merkintä kirjoitetaan muodossa O(f(n)), missä f(n) edustaa hallitsevaa termiä.
• Esimerkiksi jos hallitseva termi on n^2, Big O -merkintä olisi O(n^2).

4. Yksinkertaista merkintää (valinnainen):

• Joissakin tapauksissa Big O -brändäys n voidaan yksinkertaistaa poistamalla vakiotekijät tai käyttämällä suppeampaa merkintää.
• Esimerkiksi, O(2n) voidaan yksinkertaistaa Päällä).

Esimerkki:

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

1. Hallitseva termi: 3n³
2. Kasvujärjestys: Kuutio (n³)
3. Iso O-merkintä: O(n³)
4. Yksinkertaistettu merkintä: O(n³)

Matemaattisia esimerkkejä ajonaikaisesta analyysistä:

Alla oleva taulukko havainnollistaa erilaisten algoritmien ajonaikaista analyysiä syötteen koon (n) kasvaessa.

Algoritmisia esimerkkejä ajonaikaisesta analyysistä:

Alla oleva taulukko luokittelee algoritmit niiden ajonaikaisen monimutkaisuuden perusteella ja tarjoaa esimerkkejä jokaisesta tyypistä.

Algoritmiluokat operaatioiden lukumäärän ja suoritusajan kanssa:

Alla on algoritmien luokat ja niiden suoritusajat suoritettavassa tietokoneessa 1 miljoona toimintoa sekunnissa (1 s = 10 ⁶ μs = 10 ³ ms) :

Big O -merkinnän, Big Ω (Omega) -merkinnän ja Big θ (Theta) -merkinnän vertailu:

Alla on taulukko, jossa verrataan Big O -merkintää, Ω (Omega) -merkintää ja θ (Theta) -merkintää:

Jokaisessa merkinnässä:

• f(n) edustaa analysoitavaa funktiota, tyypillisesti algoritmin aikamonimutkaisuutta.
• g(n) edustaa tiettyä toimintoa, joka rajoittaa f(n) .
• C, C1, ja C2 ovat vakioita.
• n ₀ on pienin syötekoko, jonka ylittävä epäyhtälö pätee.

Näitä merkintöjä käytetään algoritmien analysointiin niiden perusteella pahin tapaus (Big O) , paras tapaus (Ω) , ja keskimääräinen tapaus (θ) skenaarioita.

Usein kysyttyjä kysymyksiä Big O -merkinnöistä:

Kysymys 1. Mikä on Big O -merkintä?

Vastaus: Big O Notation on matemaattinen merkintä, jota käytetään kuvaamaan algoritmin aikamonimutkaisuuden ylärajaa sen mukaan, kuinka se kasvaa syötteen kokoon nähden.

Kysymys 2. Miksi Big O -merkintä on tärkeä?

Vastaus: Se auttaa meitä analysoimaan ja vertailemaan algoritmien tehokkuutta keskittymällä pahimpaan mahdolliseen skenaarioon ja ymmärtämällä, kuinka niiden suorituskyky skaalautuu syötteen koon mukaan.

Kysymys 3. Miten Big O -merkintä lasketaan?

Vastaus: Big O -merkintä määritetään tunnistamalla hallitseva operaatio algoritmissa ja ilmaisemalla sen aikamonimutkaisuus n:llä, jossa n edustaa syötteen kokoa.

Kysymys 4. Mitä O(1) tarkoittaa suuressa O-merkinnässä?

Vastaus: O(1) tarkoittaa jatkuvaa ajan monimutkaisuutta, mikä osoittaa, että algoritmin suoritusaika ei muutu syötteen koosta riippumatta.

Kysymys 5. Mikä on erilaisten Big O -kompleksien, kuten O(log n) tai O(n^2), merkitys?

Vastaus: Erilaiset monimutkaisuudet, kuten O(log n) tai O(n^2), kuvaavat, kuinka algoritmin suorituskyky skaalautuu syötteen koon kasvaessa, mikä antaa käsityksen sen tehokkuudesta ja skaalautumisesta.

Kysymys 6. Voidaanko Big O Notationia soveltaa myös avaruuden monimutkaisuuteen?

Vastaus: Kyllä, Big O Notationia voidaan käyttää myös algoritmin tilan monimutkaisuuden analysointiin ja kuvaamiseen, mikä osoittaa, kuinka paljon muistia se vaatii suhteessa tulokokoon.

Aiheeseen liittyvä artikkeli:

• Esimerkkejä Big-O-analyysistä
• Algoritmien suunnittelu ja analyysi
• Asymptoottisten merkintöjen tyypit algoritmien kompleksisuusanalyysissä
• Algoritmien analyysi | Big – Ω (Big- Omega) merkintä
• Algoritmien analyysi | pienet o ja pienet omega-merkinnät