De efficiëntie van een algoritme hangt af van twee parameters:
- Tijdcomplexiteit
- Ruimtecomplexiteit
Tijdcomplexiteit:
Tijdcomplexiteit wordt gedefinieerd als het aantal keren dat een bepaalde instructieset wordt uitgevoerd, in plaats van de totale benodigde tijd. Dit komt omdat de totale benodigde tijd ook afhangt van een aantal externe factoren, zoals de gebruikte compiler, de snelheid van de processor, enz.
Ruimtecomplexiteit:
Ruimtecomplexiteit is de totale geheugenruimte die het programma nodig heeft voor de uitvoering ervan.
Beide worden berekend als de functie van de invoergrootte (n). Een belangrijk ding hierbij is dat ondanks deze parameters de efficiëntie van een algoritme ook afhangt van de natuur En De grootte van de invoer.
Soorten tijdcomplexiteit:
- Beste tijdcomplexiteit: Definieer de invoer waarvoor het algoritme minder tijd of minimale tijd nodig heeft. Bereken in het beste geval de ondergrens van een algoritme. Voorbeeld: Bij lineair zoeken, wanneer zoekgegevens aanwezig zijn op de eerste locatie met grote gegevens, treedt het beste geval op.
- Gemiddelde tijdcomplexiteit: Neem in het gemiddelde geval alle willekeurige invoer en bereken de rekentijd voor alle invoer.
En dan delen we het door het totale aantal ingangen. - Slechtste tijdcomplexiteit: Definieer de invoer waarvoor het algoritme lang of maximaal duurt. In het ergste geval bereken je de bovengrens van een algoritme. Voorbeeld: Bij lineair zoeken, wanneer zoekgegevens aanwezig zijn op de laatste locatie met grote gegevens, treedt het ergste geval op.
Hieronder volgt een overzicht met snelle herzieningen waar u op het laatste moment naar kunt verwijzen:
| Algoritme | Tijdcomplexiteit | Ruimtecomplexiteit | ||
|---|---|---|---|---|
| Best | Gemiddeld | Slechtst | Slechtst | |
| Selectie Sorteren | Op2) | Op2) | Op2) | O(1) |
| Bellen sorteren | Op) | Op2) | Op2) | O(1) |
| Invoegsortering | Op) | Op2) | Op2) | O(1) |
| Hoop sorteren | O(n logboek(n)) | O(n logboek(n)) | O(n logboek(n)) | O(1) |
| Snel sorteren | O(n logboek(n)) | O(n logboek(n)) | Op2) | Op) |
| Sortering samenvoegen | O(n logboek(n)) | O(n logboek(n)) | O(n logboek(n)) | Op) |
| Emmer sorteren | O(n+k) | O(n+k) | Op2) | Op) |
| Sorteer Radix | O(nk) | O(nk) | O(nk) | O(n + k) |
| Tel sorteren | O(n+k) | O(n+k) | O(n+k) | Pijl) |
| Shell-soort | O(n logboek(n)) | O(n logboek(n)) | Op2) | O(1) |
| Tim Sort | Op) | O(n logboek(n)) | O(nlog(n)) | Op) |
| Boom sorteren | O(n logboek(n)) | O(n logboek(n)) | Op2) | Op) |
| Kubus sorteren | Op) | O(n logboek(n)) | O(n logboek(n)) | Op) |
Zie ook:
- Artikelen zoeken en sorteren
- Vorig jaar GATE Vragen over sorteren
- Tijd- en ruimtecomplexiteit van invoegsortering
- Tijd- en ruimtecomplexiteit van selectiesortering
- Tijd- en ruimtecomplexiteit van bellensortering
- Tijd- en ruimtecomplexiteit van snel sorteren
- Tijd- en ruimtecomplexiteit van samenvoegsortering
- Tijd- en ruimtecomplexiteit van het Radix Sort-algoritme