Eficiența unui algoritm depinde de doi parametri:
- Complexitatea timpului
- Complexitatea spațială
Complexitatea timpului:
Complexitatea timpului este definită ca de câte ori este executat un anumit set de instrucțiuni, mai degrabă decât timpul total necesar. Se datorează faptului că timpul total necesar depinde și de unii factori externi, cum ar fi compilatorul utilizat, viteza procesorului etc.
Complexitatea spațiului:
Complexitatea spațiului este spațiul total de memorie necesar programului pentru execuția acestuia.
Ambele sunt calculate ca funcție a mărimii de intrare (n). Un lucru important aici este că, în ciuda acestor parametri, eficiența unui algoritm depinde și de natură și dimensiunea de cel intrare.
Tipuri de complexitate temporală:
- Cel mai bun timp complex: Definiți intrarea pentru care algoritmul durează mai puțin sau timp minim. În cel mai bun caz, calculați limita inferioară a unui algoritm. Exemplu: În căutarea liniară, când datele de căutare sunt prezente în prima locație a datelor mari, atunci apare cel mai bun caz.
- Complexitatea timpului mediu: În cazul mediu, luați toate intrările aleatoare și calculați timpul de calcul pentru toate intrările.
Și apoi îl împărțim la numărul total de intrări. - Cel mai rău moment complex: Definiți intrarea pentru care algoritmul durează mult sau timp maxim. În cel mai rău caz calculați limita superioară a unui algoritm. Exemplu: În căutarea liniară, când datele de căutare sunt prezente în ultima locație a datelor mari, atunci apare cel mai rău caz.
Mai jos este o fișă de revizuire rapidă la care vă puteți referi în ultimul moment:
| Algoritm | Complexitatea timpului | Complexitatea spațială | ||
|---|---|---|---|---|
| Cel mai bun | In medie | Cel mai rău | Cel mai rău | |
| Sortare selecție | Pe2) | Pe2) | Pe2) | O(1) |
| Sortare cu bule | Pe) | Pe2) | Pe2) | O(1) |
| Sortare prin inserare | Pe) | Pe2) | Pe2) | O(1) |
| Sortare grămadă | O(n log(n)) | O(n log(n)) | O(n log(n)) | O(1) |
| Sortare rapida | O(n log(n)) | O(n log(n)) | Pe2) | Pe) |
| Merge Sort | O(n log(n)) | O(n log(n)) | O(n log(n)) | Pe) |
| Sortare cu găleată | O(n +k) | O(n +k) | Pe2) | Pe) |
| Sort Radix | O(nk) | O(nk) | O(nk) | O(n + k) |
| Count Sort | O(n +k) | O(n +k) | O(n +k) | Săgeată) |
| Sortare Shell | O(n log(n)) | O(n log(n)) | Pe2) | O(1) |
| Tim Sort | Pe) | O(n log(n)) | O(nlog(n)) | Pe) |
| Sortare arbore | O(n log(n)) | O(n log(n)) | Pe2) | Pe) |
| Sortare cub | Pe) | O(n log(n)) | O(n log(n)) | Pe) |
De asemenea, vezi:
- Căutarea și sortarea articolelor
- Anul precedent Întrebări GATE despre sortare
- Timp și spațiu Complexitatea sortării inserției
- Timp și spațiu Complexitatea sortării selecției
- Complexitatea în timp și spațiu a sortării cu bule
- Timp și spațiu Complexitatea sortării rapide
- Complexitatea în timp și spațiu a sortării fuzionarii
- Complexitatea în timp și spațiu a algoritmului de sortare Radix