Algoritmo efektyvumas priklauso nuo dviejų parametrų:
- Laiko sudėtingumas
- Erdvės sudėtingumas
Laiko sudėtingumas:
Laiko sudėtingumas apibrėžiamas kaip konkretaus komandų rinkinio vykdymo kartų skaičius, o ne bendras laikas. Taip yra todėl, kad bendras laikas taip pat priklauso nuo kai kurių išorinių veiksnių, pvz., naudojamo kompiliatoriaus, procesoriaus greičio ir kt.
Erdvės sudėtingumas:
Erdvės sudėtingumas yra bendra atminties vieta, reikalinga programai vykdyti.
Abi apskaičiuojamos kaip įvesties dydžio (n) funkcija. Svarbus dalykas yra tai, kad nepaisant šių parametrų, algoritmo efektyvumas taip pat priklauso nuo gamta ir dydis į įvestis.
Laiko sudėtingumo tipai:
- Geriausio laiko sudėtingumas: Apibrėžkite įvestį, kuriai algoritmas užtrunka mažiau arba mažiausią laiką. Geriausiu atveju apskaičiuokite apatinę algoritmo ribą. Pavyzdys: atliekant linijinę paiešką, kai paieškos duomenys yra pirmoje didelių duomenų vietoje, tada įvyksta geriausias atvejis.
- Vidutinis laiko sudėtingumas: Vidutiniu atveju paimkite visas atsitiktines įvestis ir apskaičiuokite visų įėjimų skaičiavimo laiką.
Ir tada mes padalijame jį iš bendro įėjimų skaičiaus. - Blogiausio laiko sudėtingumas: Apibrėžkite įvestį, kuriam algoritmas užtrunka ilgai arba daugiausiai laiko. Blogiausiu atveju apskaičiuokite viršutinę algoritmo ribą. Pavyzdys: atliekant linijinę paiešką, kai paieškos duomenys yra paskutinėje didelių duomenų vietoje, įvyksta blogiausias atvejis.
Toliau pateikiamas greitas peržiūros lapas, kurį galite peržiūrėti paskutinę minutę:
| Algoritmas | Laiko sudėtingumas | Erdvės sudėtingumas | ||
|---|---|---|---|---|
| Geriausias | Vidutinis | Blogiausias | Blogiausias | |
| Pasirinkimas Rūšiuoti | O (n2) | O (n2) | O (n2) | O(1) |
| Burbulų rūšiavimas | O(n) | O (n2) | O (n2) | O(1) |
| Įterpimo rūšiavimas | O(n) | O (n2) | O (n2) | O(1) |
| Krūvos rūšiavimas | O(n log(n)) | O(n log(n)) | O(n log(n)) | O(1) |
| Greitas rūšiavimas | O(n log(n)) | O(n log(n)) | O (n2) | O(n) |
| Sujungti Rūšiuoti | O(n log(n)) | O(n log(n)) | O(n log(n)) | O(n) |
| Rūšiuoti kibiru | O(n +k) | O(n +k) | O (n2) | O(n) |
| Rūšiuoti Radix | O (nk) | O (nk) | O (nk) | O(n + k) |
| Skaičiuoti Rūšiuoti | O(n +k) | O(n +k) | O(n +k) | rodyklė) |
| Shell Rūšiuoti | O(n log(n)) | O(n log(n)) | O (n2) | O(1) |
| Timas Rūšiuoti | O(n) | O(n log(n)) | O(nlog(n)) | O(n) |
| Medžių rūšiavimas | O(n log(n)) | O(n log(n)) | O (n2) | O(n) |
| Rūšiuoti kubus | O(n) | O(n log(n)) | O(n log(n)) | O(n) |
Taip pat žiūrėkite:
- Straipsnių paieška ir rūšiavimas
- Ankstesnių metų GATE klausimai apie rūšiavimą
- Laiko ir erdvės įterpimo rūšiavimo sudėtingumas
- Laiko ir erdvės atrankos rūšiavimo sudėtingumas
- Laiko ir erdvės burbulų rūšiavimo sudėtingumas
- Greitojo rūšiavimo laiko ir erdvės sudėtingumas
- Sujungimo rūšiavimo laiko ir erdvės sudėtingumas
- Radix rūšiavimo algoritmo laiko ir erdvės sudėtingumas