Algoritma efektivitāte ir atkarīga no diviem parametriem:
java paziņojums
- Laika sarežģītība
- Kosmosa sarežģītība
Laika sarežģītība:
Laika sarežģītība tiek definēta kā reižu skaits, kad noteikta instrukciju kopa tiek izpildīta, nevis kopējais laiks. Tas ir tāpēc, ka kopējais nepieciešamais laiks ir atkarīgs arī no dažiem ārējiem faktoriem, piemēram, izmantotā kompilatora, procesora ātruma utt.
Kosmosa sarežģītība:
Telpas sarežģītība ir kopējā atmiņas vieta, kas programmai nepieciešama tās izpildei.
Abi tiek aprēķināti kā ievades lieluma (n) funkcija. Viena svarīga lieta šeit ir tāda, ka, neskatoties uz šiem parametriem, algoritma efektivitāte ir atkarīga arī no dabu un izmērs uz ievade.
Laika sarežģītības veidi:
- Labākā laika sarežģītība: Definējiet ievadi, kurai algoritms aizņem mazāk laika vai minimālo laiku. Labākajā gadījumā aprēķiniet algoritma apakšējo robežu. Piemērs: Lineārajā meklēšanā, kad meklēšanas dati atrodas pirmajā lielu datu atrašanās vietā, tad notiek labākais gadījums.
- Vidējā laika sarežģītība: Vidējā gadījumā ņemiet visas nejaušās ievades un aprēķiniet aprēķina laiku visām ieejām.
Un tad mēs to sadalām ar kopējo ievades skaitu. - Sliktākā laika sarežģītība: Definējiet ievadi, kurai algoritmam nepieciešams ilgs vai maksimālais laiks. Sliktākajā gadījumā aprēķiniet algoritma augšējo robežu. Piemērs: Lineārajā meklēšanā, kad meklēšanas dati atrodas pēdējā lielu datu atrašanās vietā, notiek sliktākais gadījums.
Tālāk ir sniegta ātra pārskatīšanas lapa, kuru varat atsaukties pēdējā brīdī:
| Algoritms | Laika sarežģītība | Kosmosa sarežģītība | ||
|---|---|---|---|---|
| Labākais | Vidēji | Sliktākais | Sliktākais | |
| Atlase Kārtot | O(n2) | O(n2) | O(n2) | O(1) |
| Burbuļu kārtošana | O(n) | O(n2) | O(n2) | O(1) |
| Ievietošanas kārtošana | O(n) | O(n2) | O(n2) | O(1) |
| Kaudzes kārtošana | O(n log(n)) | O(n log(n)) | O(n log(n)) | O(1) |
| Ātrā kārtošana | O(n log(n)) | O(n log(n)) | O(n2) | O(n) |
| Sapludināt Kārtot | O(n log(n)) | O(n log(n)) | O(n log(n)) | O(n) |
| Kausa kārtošana | O(n+k) | O(n+k) | O(n2) | O(n) |
| Kārtot Radix | O(nk) | O(nk) | O(nk) | O(n+k) |
| Skaits Kārtot | O(n+k) | O(n+k) | O(n+k) | bultiņa) |
| Shell Kārtot | O(n log(n)) | O(n log(n)) | O(n2) | O(1) |
| Tims Šķirots | O(n) | O(n log(n)) | O(nlog(n)) | O(n) |
| Koku šķirošana | O(n log(n)) | O(n log(n)) | O(n2) | O(n) |
| Kubu kārtošana | O(n) | O(n log(n)) | O(n log(n)) | O(n) |
Skatiet arī:
- Rakstu meklēšana un šķirošana
- Iepriekšējā gada GATE Jautājumi par šķirošanu
- Ievietošanas kārtošanas laika un telpas sarežģītība
- Atlases kārtošanas laika un telpas sarežģītība
- Burbuļu kārtošanas laika un telpas sarežģītība
- Ātrās šķirošanas laika un telpas sarežģītība
- Sapludināšanas kārtošanas laika un telpas sarežģītība
- Radix šķirošanas algoritma laika un telpas sarežģītība