Effektiviteten til en algoritme avhenger av to parametere:
- Tidskompleksitet
- Plass kompleksitet
Tidskompleksitet:
Tidskompleksitet er definert som antall ganger et bestemt instruksjonssett blir utført i stedet for den totale tiden det tar. Det er fordi den totale tiden det tar også avhenger av noen eksterne faktorer som kompilatoren som brukes, prosessorens hastighet, etc.
Plass kompleksitet:
Plasskompleksitet er den totale minneplassen som kreves av programmet for utførelse.
Begge beregnes som funksjonen av inngangsstørrelse(n). En viktig ting her er at til tross for disse parameterne, avhenger effektiviteten til en algoritme også av natur og størrelsen av de input.
Typer tidskompleksitet:
- Beste tidskompleksitet: Definer inngangen som algoritmen tar kortere tid eller minimumstid for. Beregn i beste fall den nedre grensen til en algoritme. Eksempel: I det lineære søket når søkedata er tilstede på den første plasseringen av store data, oppstår det beste tilfellet.
- Gjennomsnittlig tidskompleksitet: I gjennomsnittlig tilfelle ta alle tilfeldige innganger og beregn beregningstiden for alle innganger.
Og så deler vi det på det totale antallet innganger. - Verste tidskompleksitet: Definer inngangen for hvilken algoritme tar lang tid eller maksimal tid. I verste fall beregner den øvre grensen til en algoritme. Eksempel: I det lineære søket når søkedata er tilstede på den siste plasseringen av store data, skjer det verste tilfellet.
Følgende er et raskt revisjonsark som du kan referere til i siste liten:
| Algoritme | Tidskompleksitet | Plass kompleksitet | ||
|---|---|---|---|---|
| Beste | Gjennomsnitt | Verst | Verst | |
| Utvalgssortering | På2) | På2) | På2) | O(1) |
| Boblesortering | På) | På2) | På2) | O(1) |
| Innsettingssortering | På) | På2) | På2) | O(1) |
| Heap Sorter | O(n log(n)) | O(n log(n)) | O(n log(n)) | O(1) |
| Rask sortering | O(n log(n)) | O(n log(n)) | På2) | På) |
| Slå sammen sortering | O(n log(n)) | O(n log(n)) | O(n log(n)) | På) |
| Bøttesortering | O(n +k) | O(n +k) | På2) | På) |
| Sorter Radix | O(nk) | O(nk) | O(nk) | O(n + k) |
| Telle Sorter | O(n +k) | O(n +k) | O(n +k) | Pil) |
| Skall sortering | O(n log(n)) | O(n log(n)) | På2) | O(1) |
| Tim Sort | På) | O(n log(n)) | O(nlog(n)) | På) |
| Tre sortering | O(n log(n)) | O(n log(n)) | På2) | På) |
| Kube sortering | På) | O(n log(n)) | O(n log(n)) | På) |
Se også:
- Søke og sortere artikler
- Forrige år GATE Spørsmål om sortering
- Tid og rom kompleksitet ved innsettingssortering
- Tid og rom kompleksiteten til utvalgssortering
- Tid og rom kompleksiteten til boblesortering
- Tid og rom kompleksiteten til rask sortering
- Tid og rom kompleksiteten til sammenslåingssortering
- Tid og rom kompleksiteten til Radix Sort Algorithm