Účinnosť algoritmu závisí od dvoch parametrov:
- Časová zložitosť
- Priestorová zložitosť
Časová zložitosť:
Časová zložitosť je definovaná ako počet vykonaní konkrétnej inštrukčnej sady, a nie ako celkový čas. Je to preto, že celkový čas závisí aj od niektorých vonkajších faktorov, ako je použitý kompilátor, rýchlosť procesora atď.
Priestorová zložitosť:
Priestorová zložitosť je celkový pamäťový priestor, ktorý program potrebuje na svoje vykonanie.
Obe sú vypočítané ako funkcia vstupnej veľkosti (n). Jedna dôležitá vec je, že napriek týmto parametrom závisí účinnosť algoritmu aj od prírody a veľkosť a vstup.
Druhy časovej zložitosti:
- Najlepšia časová zložitosť: Definujte vstup, pre ktorý algoritmus zaberie menej času alebo minimálny čas. V najlepšom prípade vypočítajte spodnú hranicu algoritmu. Príklad: Pri lineárnom vyhľadávaní, keď sú údaje vyhľadávania prítomné na prvom mieste veľkých údajov, nastáva najlepší prípad.
- Priemerná časová zložitosť: V priemernom prípade vezmite všetky náhodné vstupy a vypočítajte čas výpočtu pre všetky vstupy.
A potom to vydelíme celkovým počtom vstupov. - Najhoršia časová zložitosť: Definujte vstup, pre ktorý algoritmus trvá dlho alebo maximálne. V najhoršom prípade vypočítajte hornú hranicu algoritmu. Príklad: Pri lineárnom vyhľadávaní, keď sa údaje vyhľadávania nachádzajú na poslednom mieste veľkých údajov, nastáva najhorší prípad.
Nasleduje rýchly revízny list, ktorý si môžete na poslednú chvíľu pozrieť:
| Algoritmus | Časová zložitosť | Vesmírna zložitosť | ||
|---|---|---|---|---|
| Najlepšie | Priemerná | Najhoršie | Najhoršie | |
| Výber Zoradiť | O(n2) | O(n2) | O(n2) | O(1) |
| Bublinové triedenie | O(n) | O(n2) | O(n2) | O(1) |
| Triedenie vloženia | O(n) | O(n2) | O(n2) | O(1) |
| Hromadné triedenie | O(n log(n)) | O(n log(n)) | O(n log(n)) | O(1) |
| Rýchle triedenie | O(n log(n)) | O(n log(n)) | O(n2) | O(n) |
| Zlúčiť triedenie | O(n log(n)) | O(n log(n)) | O(n log(n)) | O(n) |
| Triediť vedro | O(n + k) | O(n + k) | O(n2) | O(n) |
| Zoradiť Radix | O(nk) | O(nk) | O(nk) | O(n + k) |
| Počet Triediť | O(n + k) | O(n + k) | O(n + k) | šípka) |
| 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) |
| Triedenie stromov | O(n log(n)) | O(n log(n)) | O(n2) | O(n) |
| Cube Tried | O(n) | O(n log(n)) | O(n log(n)) | O(n) |
Pozri tiež:
- Vyhľadávanie a triedenie článkov
- Predchádzajúci rok GATE Otázky o triedení
- Časová a priestorová zložitosť zoradenia vloženia
- Časová a priestorová zložitosť triedenia výberu
- Časová a priestorová zložitosť bublinkového triedenia
- Časová a priestorová zložitosť rýchleho triedenia
- Časová a priestorová zložitosť triedenia zlúčenia
- Časová a priestorová zložitosť Radixovho triediaceho algoritmu