Didelis O žymėjimas yra galingas įrankis, naudojamas kompiuterių moksle, apibūdinantis algoritmų sudėtingumą laike arba erdvėje. Tai standartizuotas būdas palyginti skirtingų algoritmų efektyvumą, atsižvelgiant į jų blogiausio atvejo veikimą. Supratimas Didelis O žymėjimas yra būtinas norint analizuoti ir kurti efektyvius algoritmus.

Šioje pamokoje apžvelgsime pagrindus Didelis O žymėjimas , jo reikšmę ir kaip analizuoti algoritmų sudėtingumą naudojant Didysis O .

Turinys

• Kas yra „Big-O“ žymėjimas?
• Big-O žymėjimo apibrėžimas:
• Kodėl „Big O“ žymėjimas yra svarbus?
• Didžiojo O žymėjimo savybės
• Bendrieji Big-O žymėjimai
• Kaip nustatyti didžiąją O žymą?
• Matematiniai vykdymo laiko analizės pavyzdžiai
• Algoritminiai vykdymo laiko analizės pavyzdžiai
• Algoritmų klasės su operacijų skaičiumi ir vykdymo laiku
• Didžiojo O žymėjimo, didžiojo Ω (Omega) žymėjimo ir didžiojo θ (teta) žymėjimo palyginimas
• Dažnai užduodami klausimai apie „Big O“ žymėjimą

Kas yra „Big-O“ žymėjimas?

Didysis-O , paprastai vadinamas Užsakymas , yra būdas išreikšti viršutinė riba algoritmo sudėtingumo laike, nes jis analizuoja blogiausiu atveju algoritmo situacija. Tai suteikia an viršutinis limitas apie laiką, kurį algoritmas užima pagal įvesties dydį. Jis žymimas kaip O(f(n)) , kur f(n) yra funkcija, nurodanti operacijų (žingsnių), kuriuos algoritmas atlieka norėdamas išspręsti dydžio problemą, skaičių n .

Big-O žymėjimas naudojamas algoritmo veikimui ar sudėtingumui apibūdinti. Konkrečiai, jis apibūdina Blogiausias scenarijus kalbant apie laikas arba erdvės sudėtingumas.

Svarbus punktas:

• Didelis O žymėjimas apibūdina tik asimptotinį funkcijos elgesį, o ne tikslią jos reikšmę.
• The Didelis O žymėjimas gali būti naudojamas skirtingų algoritmų ar duomenų struktūrų efektyvumui palyginti.

Big-O žymėjimo apibrėžimas:

Suteiktos dvi funkcijos f(n) ir g(n) , mes taip sakome f(n) yra O(g(n)) jei egzistuoja konstantos c> 0 ir n ₀ >= 0 toks f(n) <= c*g(n) visiems n>= n ₀ .

Paprasčiau tariant, f(n) yra O(g(n)) jeigu f(n) auga ne greičiau kaip c*g(n) visiems n>= n₀kur c ir n₀yra konstantos.

Kodėl „Big O“ žymėjimas yra svarbus?

„Big O“ žymėjimas yra matematinis žymėjimas, naudojamas apibūdinti blogiausio atvejo algoritmo sudėtingumą arba efektyvumą arba blogiausią duomenų struktūros erdvės sudėtingumą. Tai suteikia galimybę palyginti skirtingų algoritmų ir duomenų struktūrų našumą ir numatyti, kaip jie elgsis didėjant įvesties dydžiui.

Didelis O žymėjimas svarbus dėl kelių priežasčių:

• Big O žymėjimas yra svarbus, nes padeda analizuoti algoritmų efektyvumą.
• Jame pateikiamas būdas apibūdinti, kaip vykdymo laikas arba erdvės reikalavimai algoritmo dydis didėja didėjant įvesties dydžiui.
• Leidžia programuotojams palyginti skirtingus algoritmus ir pasirinkti efektyviausią konkrečiai problemai spręsti.
• Padeda suprasti algoritmų mastelį ir numatyti, kaip jie veiks augant įvesties dydžiui.
• Leidžia kūrėjams optimizuoti kodą ir pagerinti bendrą našumą.

Didžiojo O žymėjimo savybės:

Žemiau yra keletas svarbių „Big O“ žymėjimo savybių:

1. Refleksyvumas:

Bet kuriai funkcijai f(n) f(n) = O(f(n)).

Pavyzdys:

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

2. Tranzityvumas:

Jei f(n) = O(g(n)) ir g(n) = O(h(n)), tai f(n) = O(h(n)).

Pavyzdys:

f(n) = n³, g(n) = n², h(n) = n⁴. Tada f(n) = O(g(n)) ir g(n) = O(h(n)). Todėl f(n) = O(h(n)).

3. Pastovus koeficientas:

Bet kuriai konstantai c> 0 ir funkcijoms f(n) ir g(n), jei f(n) = O(g(n)), tai cf(n) = O(g(n)).

Pavyzdys:

f(n) = n, g(n) = n². Tada f(n) = O(g(n)). Todėl 2f(n) = O(g(n)).

4. Sumos taisyklė:

Jei f(n) = O(g(n)) ir h(n) = O(g(n)), tai f(n) + h(n) = O(g(n)).

Pavyzdys:

f(n) = n², g(n) = n³, h(n) = n⁴. Tada f(n) = O(g(n)) ir h(n) = O(g(n)). Todėl f(n) + h(n) = O(g(n)).

5. Gaminio taisyklė:

Jei f(n) = O(g(n)) ir h(n) = O(k(n)), tai f(n) * h(n) = O(g(n) * k(n)) .

Pavyzdys:

f(n) = n, g(n) = n², h(n) = n³, k(n) = n⁴. Tada f(n) = O(g(n)) ir h(n) = O(k(n)). Todėl f(n) * h(n) = O(g(n) * k(n)) = O(n)⁵).

6. Sudėties taisyklė:

Jei f(n) = O(g(n)) ir g(n) = O(h(n)), tai f(g(n)) = O(h(n)).

Pavyzdys:

f(n) = n², g(n) = n, h(n) = n³. Tada f(n) = O(g(n)) ir g(n) = O(h(n)). Todėl f(g(n)) = O(h(n)) = O(n³).

Įprasti „Big-O“ žymėjimai:

Big-O žymėjimas yra būdas išmatuoti algoritmo laiko ir erdvės sudėtingumą. Jame aprašoma viršutinė sudėtingumo riba pagal blogiausią scenarijų. Pažvelkime į skirtingus laiko sudėtingumo tipus:

1. Linijinis laiko sudėtingumas: didelis O(n) sudėtingumas

Linijinis laiko sudėtingumas reiškia, kad algoritmo veikimo laikas didėja tiesiškai didėjant įvesties dydžiui.

Pavyzdžiui, apsvarstykite algoritmą, kuris eina per masyvą, kad surastų konkretų elementą :

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

2. Logaritminis laiko sudėtingumas: didelis O(log n) sudėtingumas

Logaritminis laiko sudėtingumas reiškia, kad algoritmo veikimo laikas yra proporcingas įvesties dydžio logaritmui.

Pavyzdžiui, a dvejetainis paieškos algoritmas turi logaritminį laiko sudėtingumą:

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);  } grįžti -1; }>

3. Kvadratinis laiko sudėtingumas: didelis O(n²) Sudėtingumas

Kvadratinis laiko sudėtingumas reiškia, kad algoritmo veikimo laikas yra proporcingas įvesties dydžio kvadratui.

Pavyzdžiui, paprastas burbulų rūšiavimo algoritmas turi kvadratinį laiko sudėtingumą:

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

4. Kubinio laiko sudėtingumas: didelis O(n³) Sudėtingumas

Kubinis laiko sudėtingumas reiškia, kad algoritmo veikimo laikas yra proporcingas įvesties dydžio kubui.

Pavyzdžiui, naivuolis matricos daugybos algoritmas turi kubinį laiko sudėtingumą:

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. Polinominis laiko sudėtingumas: didelis O(n^k) Sudėtingumas

Polinominis laiko sudėtingumas reiškia algoritmo sudėtingumą laike, kuris gali būti išreikštas kaip įvesties dydžio daugianario funkcija n . Didelėje O Sakoma, kad algoritmas turi daugianario laiko sudėtingumą, jei jo sudėtingumas yra toks O (n ^k ) , kur k yra konstanta ir reiškia daugianario laipsnį.

Dauginamo laiko sudėtingumo algoritmai paprastai laikomi efektyviais, nes didėjant įvesties dydžiui, veikimo laikas auga protingai. Įprasti daugianario laiko sudėtingumo algoritmų pavyzdžiai: tiesinis laiko sudėtingumas O(n) , kvadratinis laiko sudėtingumas O(n ² ) , ir kubinis laiko sudėtingumas O(n ³ ) .

6. Eksponentinis laiko sudėtingumas: didelis O(2ⁿ) Sudėtingumas

Eksponentinis laiko sudėtingumas reiškia, kad algoritmo veikimo laikas padvigubėja kiekvieną kartą papildant įvesties duomenų rinkinį.

normalizavimas duomenų bazėje

Pavyzdžiui, problema generuojant visus aibės poaibius yra eksponentinio laiko sudėtingumo:

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

Faktinis laiko sudėtingumas: didelis O(n!) sudėtingumas

Faktinis laiko sudėtingumas reiškia, kad algoritmo veikimo laikas didėja priklausomai nuo įvesties dydžio. Tai dažnai pastebima algoritmuose, kurie generuoja visas duomenų rinkinio permutacijas.

Štai faktorinio laiko sudėtingumo algoritmo, kuris generuoja visas masyvo permutacijas, pavyzdys:

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

Jei pavaizduotume dažniausiai pasitaikančius Big O žymėjimo pavyzdžius, gautume tokį grafiką:

Kaip nustatyti didžiąją O žymą?

Didelis O žymėjimas yra matematinis žymėjimas, naudojamas apibūdinti asimptotinis elgesys funkcijos, nes jos įvestis tampa be galo didelė. Tai yra būdas apibūdinti algoritmų ir duomenų struktūrų efektyvumą.

Veiksmai, skirti nustatyti didžiąją O žymą:

1. Nustatykite dominuojantį terminą:

• Išnagrinėkite funkciją ir nustatykite terminą su didžiausiu augimo laipsniu, kai įvesties dydis didėja.
• Nepaisykite jokių pastovių veiksnių arba žemesnės eilės terminų.

2. Nustatykite augimo tvarką:

• Dominuojančio termino augimo tvarka lemia Big O žymėjimą.

3. Parašykite didžiąją O žymą:

• Didysis O žymėjimas rašomas kaip O(f(n)), kur f(n) reiškia dominuojantį terminą.
• Pavyzdžiui, jei dominuojantis terminas yra n^2, Big O žymėjimas būtų O(n^2).

4. Supaprastinkite žymėjimą (nebūtina):

• Kai kuriais atvejais, Big O prekės ženklas n galima supaprastinti pašalinus pastovius veiksnius arba naudojant glaustesnį žymėjimą.
• Pavyzdžiui, O(2n) galima supaprastinti iki O(n).

Pavyzdys:

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

1. Dominuojantis terminas: 3n³
2. Augimo tvarka: kubinis (n³)
3. Didelis O žymėjimas: O (n³)
4. Supaprastintas žymėjimas: O(n³)

Matematiniai vykdymo laiko analizės pavyzdžiai:

Žemiau esančioje lentelėje parodyta skirtingų algoritmų eilių vykdymo analizė, kai didėja įvesties dydis (n).

Algoritminiai vykdymo laiko analizės pavyzdžiai:

Žemiau esančioje lentelėje algoritmai skirstomi į kategorijas pagal jų vykdymo sudėtingumą ir pateikiami kiekvieno tipo pavyzdžiai.

Algoritmų klasės su operacijų skaičiumi ir vykdymo laiku:

Žemiau pateikiamos algoritmų klasės ir jų vykdymo laikas vykdomame kompiuteryje 1 milijonas operacijų per sekundę (1 sek. = 10 ⁶ μs = 10 ³ msek) :

Didžiojo O žymėjimo, didžiojo Ω (Omega) žymėjimo ir didžiojo θ (teta) žymėjimo palyginimas:

Žemiau yra lentelė, kurioje lyginami Big O, Ω (Omega) ir θ (Theta) žymėjimai:

Kiekviename užraše:

• f(n) reiškia analizuojamą funkciją, paprastai algoritmo sudėtingumą laiku.
• g(n) reiškia konkrečią funkciją, kuri ribojasi f(n) .
• C, C1, ir C2 yra konstantos.
• n ₀ yra mažiausias įvesties dydis, už kurį galioja nelygybė.

Šie žymėjimai naudojami analizuojant algoritmus, pagrįstus jais blogiausias atvejis (Big O) , geriausiu atveju (Ω) , ir vidutinė raidė (θ) scenarijai.

Dažnai užduodami klausimai apie „Big O“ žymėjimą:

1 klausimas. Kas yra Big O žymėjimas?

Atsakymas: Big O žymėjimas yra matematinis žymėjimas, naudojamas apibūdinti algoritmo laiko sudėtingumo viršutinę ribą, atsižvelgiant į tai, kaip jis auga, palyginti su įvesties dydžiu.

2 klausimas. Kodėl Big O žymėjimas yra svarbus?

Atsakymas: Tai padeda mums analizuoti ir palyginti algoritmų efektyvumą sutelkiant dėmesį į blogiausią scenarijų ir suprasti, kaip jų našumas keičiasi atsižvelgiant į įvesties dydį.

3 klausimas. Kaip apskaičiuojamas didelis O žymėjimas?

Atsakymas: Didysis O žymėjimas nustatomas identifikuojant dominuojančią algoritmo operaciją ir išreiškiant jos laiko sudėtingumą n, kur n reiškia įvesties dydį.

4 klausimas. Ką reiškia O(1) didžiajame O žymėjime?

Atsakymas: O (1) reiškia pastovų laiko sudėtingumą, o tai rodo, kad algoritmo vykdymo laikas nesikeičia nepriklausomai nuo įvesties dydžio.

5 klausimas. Kokią reikšmę turi skirtingi dideli O sudėtingumai, tokie kaip O(log n) arba O(n^2)?

Atsakymas: Įvairūs sudėtingumo rodikliai, pvz., O(log n) arba O(n^2), rodo, kaip didėja algoritmo našumas didėjant įvesties dydžiui, o tai suteikia įžvalgų apie jo efektyvumą ir mastelį.

6 klausimas. Ar Big O žymėjimas gali būti pritaikytas ir erdvės sudėtingumui?

Atsakymas: Taip, Big O notation taip pat gali būti naudojamas algoritmo erdvės sudėtingumui analizuoti ir apibūdinti, nurodant, kiek atminties jam reikia, palyginti su įvesties dydžiu.

Susijęs straipsnis:

• Big-O analizės pavyzdžiai
• Algoritmų projektavimas ir analizė
• Asimptotinių žymėjimų tipai algoritmų sudėtingumo analizėje
• Algoritmų analizė | Didelis – Ω (Big- Omega) žymėjimas
• Algoritmų analizė | maži o ir maži omega užrašai