Effektiviteten hos en algoritm beror på två parametrar:
- Tidskomplexitet
- Rymdkomplexitet
Tidskomplexitet:
Tidskomplexitet definieras som antalet gånger en viss instruktionsuppsättning exekveras snarare än den totala tiden det tar. Det beror på att den totala tiden det tar beror också på vissa externa faktorer som kompilatorn som används, processorns hastighet etc.
Utrymmes komplexitet:
Space Complexity är det totala minnesutrymme som krävs av programmet för dess exekvering.
Båda beräknas som funktionen av ingångsstorlek(n). En viktig sak här är att trots dessa parametrar beror effektiviteten hos en algoritm också på natur och storlek av de inmatning.
Typer av tidskomplexitet:
- Bästa tidskomplexitet: Definiera ingången för vilken algoritmen tar kortare tid eller minsta tid. I bästa fall beräkna den nedre gränsen för en algoritm. Exempel: I den linjära sökningen när sökdata finns på den första platsen för stora data så inträffar det bästa fallet.
- Genomsnittlig tidskomplexitet: Ta i genomsnitt alla slumpmässiga ingångar och beräkna beräkningstiden för alla ingångar.
Och sedan dividerar vi det med det totala antalet ingångar. - Värsta tidskomplexitet: Definiera ingången för vilken algoritm tar lång tid eller maximal tid. I värsta fall beräkna den övre gränsen för en algoritm. Exempel: I den linjära sökningen när sökdata finns på den sista platsen för stor data inträffar det värsta fallet.
Följande är ett snabbrevisionsblad som du kan hänvisa till i sista minuten:
| Algoritm | Tidskomplexitet | Rymdkomplexitet | ||
|---|---|---|---|---|
| Bäst | Genomsnitt | Värst | Värst | |
| Urval Sortera | På2) | På2) | På2) | O(1) |
| Bubblesort | På) | På2) | På2) | O(1) |
| Insättningssortering | På) | På2) | På2) | O(1) |
| Hög sortering | O(n log(n)) | O(n log(n)) | O(n log(n)) | O(1) |
| Snabb sortering | O(n log(n)) | O(n log(n)) | På2) | På) |
| Sammanfoga sortering | O(n log(n)) | O(n log(n)) | O(n log(n)) | På) |
| Hinksortering | O(n +k) | O(n +k) | På2) | På) |
| Sortera Radix | O(nk) | O(nk) | O(nk) | O(n + k) |
| Räkna Sortera | O(n +k) | O(n +k) | O(n +k) | Pil) |
| Skalsortering | O(n log(n)) | O(n log(n)) | På2) | O(1) |
| Tim Sort | På) | O(n log(n)) | O(nlog(n)) | På) |
| Trädsortering | O(n log(n)) | O(n log(n)) | På2) | På) |
| Kubsortering | På) | O(n log(n)) | O(n log(n)) | På) |
Se även:
- Söka och sortera artiklar
- Föregående år GATE-frågor om sortering
- Tid och rumskomplexitet för insättningssortering
- Tid och rumskomplexitet i urvalssortering
- Tid och rumskomplexitet av Bubblesort
- Tid och rumskomplexitet för snabb sortering
- Tid och rumskomplexitet för sammanslagningssortering
- Tid och rumskomplexitet hos Radix Sort Algorithm