Tidskompleksiteter af alle sorteringsalgoritmer
Effektiviteten af en algoritme afhænger af to parametre:
- Tidskompleksitet
- Rumkompleksitet
Tidskompleksitet:
Tidskompleksitet er defineret som antallet af gange, et bestemt instruktionssæt udføres i stedet for den samlede tid, det tager. Det er fordi den samlede tid, det tager, også afhænger af nogle eksterne faktorer som den anvendte compiler, processorens hastighed osv.
Rumkompleksitet:
Rumkompleksitet er den samlede hukommelsesplads, der kræves af programmet til dets udførelse.
Begge beregnes som funktionen af inputstørrelse(n). En vigtig ting her er, at på trods af disse parametre afhænger effektiviteten af en algoritme også af natur og størrelse på det input.
Typer af tidskompleksitet:
- Bedste tidskompleksitet: Definer det input, som algoritmen tager kortere tid eller minimumstid for. I bedste tilfælde beregnes den nedre grænse for en algoritme. Eksempel: I den lineære søgning, når søgedata er til stede på den første placering af store data, så forekommer det bedste tilfælde.
- Gennemsnitlig tidskompleksitet: Tag i gennemsnittet alle tilfældige input og beregn beregningstiden for alle input.
Og så dividerer vi det med det samlede antal input. - Værste tidskompleksitet: Definer input, for hvilken algoritme tager lang tid eller maksimal tid. I værste fald udregn den øvre grænse for en algoritme. Eksempel: I den lineære søgning, når søgedata er til stede på den sidste placering af store data, opstår det værste tilfælde.
Følgende er et hurtigt revisionsark, som du kan henvise til i sidste øjeblik:
| Algoritme | Tidskompleksitet | Rumkompleksitet | ||
|---|---|---|---|---|
| Bedst | Gennemsnit | Værst | Værst | |
| Udvalgssortering | På 2 ) | På 2 ) | På 2 ) | O(1) |
| Boble sortering | På) | På 2 ) | På 2 ) | O(1) |
| Indsættelsessortering | På) | På 2 ) | På 2 ) | O(1) |
| Dynge sortering | O(n log(n)) | O(n log(n)) | O(n log(n)) | O(1) |
| Hurtig sortering | O(n log(n)) | O(n log(n)) | På 2 ) | På) |
| Flet sortering | O(n log(n)) | O(n log(n)) | O(n log(n)) | På) |
| Sortér spand | O(n +k) | O(n +k) | På 2 ) | På) |
| Sortér Radix | O(nk) | O(nk) | O(nk) | O(n + k) |
| Tæl Sorter | O(n +k) | O(n +k) | O(n +k) | Pil) |
| Skal sortering | O(n log(n)) | O(n log(n)) | På 2 ) | O(1) |
| Tim Sort | På) | O(n log(n)) | O(nlog(n)) | På) |
| Træ sortering | O(n log(n)) | O(n log(n)) | På 2 ) | På) |
| Terningssortering | På) | O(n log(n)) | O(n log(n)) | På) |
Se også:
- Søgning og sortering af artikler
- Forrige år GATE Spørgsmål om sortering
- Tid og rum kompleksitet af indsættelsessortering
- Tid og rum Kompleksitet af udvalgssortering
- Tid og rum kompleksitet af boblesortering
- Tid og rum kompleksitet af hurtig sortering
- Tid og rum kompleksitet af Merge Sort
- Tid og rum kompleksitet af Radix Sort Algorithm
