Učinkovitost algoritma je odvisna od dveh parametrov:
pretvorba niza v objekt json
- Časovna zapletenost
- Kompleksnost prostora
Časovna zapletenost:
Časovna kompleksnost je opredeljena kot število, kolikokrat se določen niz navodil izvede, in ne skupni čas, ki je porabljen. To je zato, ker je skupni porabljen čas odvisen tudi od nekaterih zunanjih dejavnikov, kot so uporabljeni prevajalnik, hitrost procesorja itd.
Kompleksnost prostora:
Kompleksnost prostora je skupni pomnilniški prostor, ki ga program potrebuje za svojo izvedbo.
Oboje se izračuna kot funkcija vhodne velikosti (n). Ena pomembna stvar pri tem je, da je kljub tem parametrom učinkovitost algoritma odvisna tudi od narave in velikost the vnos.
Vrste časovne zapletenosti:
- Najboljša časovna kompleksnost: Določite vnos, za katerega algoritem potrebuje manj časa ali najmanj časa. V najboljšem primeru izračunajte spodnjo mejo algoritma. Primer: pri linearnem iskanju, ko so iskalni podatki prisotni na prvi lokaciji velikih podatkov, pride do najboljšega primera.
- Povprečna časovna zahtevnost: V povprečnem primeru vzemite vse naključne vnose in izračunajte čas izračuna za vse vnose.
Nato ga delimo s skupnim številom vnosov. - Najslabša časovna kompleksnost: Določite vnos, za katerega algoritem potrebuje dolgo časa ali največ časa. V najslabšem primeru izračunajte zgornjo mejo algoritma. Primer: pri linearnem iskanju, ko so iskalni podatki prisotni na zadnji lokaciji velikih podatkov, pride do najslabšega primera.
Sledi hitra revizijska lista, na katero se lahko obrnete v zadnjem trenutku:
| Algoritem | Časovna zapletenost | Kompleksnost prostora | ||
|---|---|---|---|---|
| najboljše | Povprečje | Najslabše | Najslabše | |
| Izbor Razvrsti | O(n2) | O(n2) | O(n2) | O(1) |
| Bubble Sort | O(n) | O(n2) | O(n2) | O(1) |
| Razvrščanje vstavljanja | O(n) | O(n2) | O(n2) | O(1) |
| Razvrščanje kopice | O(n log(n)) | O(n log(n)) | O(n log(n)) | O(1) |
| Hitro razvrščanje | O(n log(n)) | O(n log(n)) | O(n2) | O(n) |
| Spoji Razvrsti | O(n log(n)) | O(n log(n)) | O(n log(n)) | O(n) |
| Razvrščanje vedra | O(n +k) | O(n +k) | O(n2) | O(n) |
| Razvrsti Radix | O(nk) | O(nk) | O(nk) | O(n + k) |
| Število Razvrščanje | O(n +k) | O(n +k) | O(n +k) | puščica) |
| Shell Sort | O(n log(n)) | O(n log(n)) | O(n2) | O(1) |
| Tim Sort | O(n) | O(n log(n)) | O(nlog(n)) | O(n) |
| Drevesna vrsta | O(n log(n)) | O(n log(n)) | O(n2) | O(n) |
| Razvrščanje kocke | O(n) | O(n log(n)) | O(n log(n)) | O(n) |
Glej tudi:
- Iskanje in razvrščanje člankov
- Prejšnje leto GATE vprašanja o razvrščanju
- Časovna in prostorska kompleksnost razvrščanja z vstavljanjem
- Časovna in prostorska kompleksnost izbirnega razvrščanja
- Časovna in prostorska kompleksnost Bubble Sort
- Časovna in prostorska kompleksnost hitrega razvrščanja
- Časovna in prostorska kompleksnost razvrščanja z zlivanjem
- Časovna in prostorska kompleksnost algoritma razvrščanja Radix