Algoritmin tehokkuus riippuu kahdesta parametrista:
attribuuttivirhe python
- Aika monimutkaisuus
- Avaruuden monimutkaisuus
Aika monimutkaisuus:
Aika monimutkaisuus määritellään kuinka monta kertaa tietty käskyjoukko on suoritettu kuluneen kokonaisajan sijaan. Tämä johtuu siitä, että käytetty kokonaisaika riippuu myös joistakin ulkoisista tekijöistä, kuten käytetystä kääntäjästä, prosessorin nopeudesta jne.
Tilan monimutkaisuus:
Tilan monimutkaisuus on ohjelman suorittamiseen tarvittava kokonaismuistitila.
Molemmat lasketaan syötteen koon (n) funktiona. Yksi tärkeä asia tässä on, että näistä parametreista huolimatta algoritmin tehokkuus riippuu myös luonto ja koko the syöttö.
Ajan monimutkaisuuden tyypit:
- Paras aika monimutkaisuus: Määritä syöte, jolle algoritmi vie vähemmän aikaa tai minimiaika. Parhaassa tapauksessa laske algoritmin alaraja. Esimerkki: Lineaarisessa haussa, kun hakudataa on suuren datan ensimmäisessä paikassa, tapahtuu paras tapaus.
- Keskimääräinen aika monimutkaisuus: Keskimääräisessä tapauksessa ota kaikki satunnaiset syötteet ja laske kaikkien syötteiden laskenta-aika.
Ja sitten jaamme sen syötteiden kokonaismäärällä. - Huonoimman ajan monimutkaisuus: Määritä syöte, jolle algoritmi kestää kauan tai maksimiaika. Pahimmassa tapauksessa laske algoritmin yläraja. Esimerkki: Lineaarisessa haussa, kun hakudataa on suuren datan viimeisessä paikassa, tapahtuu pahin tapaus.
Seuraavassa on nopea tarkistuslomake, johon voit viitata viime hetkellä:
| Algoritmi | Aika monimutkaisuus | Avaruuden monimutkaisuus | ||
|---|---|---|---|---|
| Parhaat | Keskiverto | Huonoin | Huonoin | |
| Valinta Lajittele | Päällä2) | Päällä2) | Päällä2) | O(1) |
| Kuplalajittelu | Päällä) | Päällä2) | Päällä2) | O(1) |
| Lisäys Lajittele | Päällä) | Päällä2) | Päällä2) | O(1) |
| Keon lajittelu | O(n log(n)) | O(n log(n)) | O(n log(n)) | O(1) |
| Nopea lajittelu | O(n log(n)) | O(n log(n)) | Päällä2) | Päällä) |
| Yhdistä lajittelu | O(n log(n)) | O(n log(n)) | O(n log(n)) | Päällä) |
| Kauhan lajittelu | O(n +k) | O(n +k) | Päällä2) | Päällä) |
| Lajittele Radix | O(nk) | O(nk) | O(nk) | O(n + k) |
| Count Lajittele | O(n +k) | O(n +k) | O(n +k) | Nuoli) |
| Shell Lajittele | O(n log(n)) | O(n log(n)) | Päällä2) | O(1) |
| Tim Sort | Päällä) | O(n log(n)) | O(nlog(n)) | Päällä) |
| Puulajittelu | O(n log(n)) | O(n log(n)) | Päällä2) | Päällä) |
| Kuutioiden lajittelu | Päällä) | O(n log(n)) | O(n log(n)) | Päällä) |
Katso myös:
- Artikkelien haku ja lajittelu
- Edellisen vuoden GATE-kysymykset lajittelusta
- Aika ja tila -lisäyksen monimutkaisuus
- Aika- ja tilalajittelun monimutkaisuus
- Kuplalajittelun aika ja tila monimutkaisuus
- Pikalajittelun aika ja tila monimutkaisuus
- Yhdistelmälajittelun aika ja tila monimutkaisuus
- Radix-lajittelualgoritmin aika ja tila monimutkaisuus