L'eficiència d'un algorisme depèn de dos paràmetres:
emojis d'iphone al telèfon Android
- Complexitat temporal
- Complexitat espacial
Complexitat temporal:
La complexitat del temps es defineix com el nombre de vegades que s'executa un conjunt d'instruccions concret en lloc del temps total que es triga. És perquè el temps total que es triga també depèn d'alguns factors externs com el compilador utilitzat, la velocitat del processador, etc.
Complexitat espacial:
La complexitat de l'espai és l'espai total de memòria requerit pel programa per a la seva execució.
Tots dos es calculen com a funció de la mida d'entrada (n). Una cosa important aquí és que, malgrat aquests paràmetres, l'eficiència d'un algorisme també depèn de naturalesa i mida de el entrada.
Tipus de complexitat temporal:
- Millor complexitat temporal: Definiu l'entrada per a la qual l'algorisme triga menys temps o temps mínim. En el millor dels casos, calculeu el límit inferior d'un algorisme. Exemple: a la cerca lineal, quan les dades de cerca estan presents a la primera ubicació de dades grans, es produeix el millor dels casos.
- Complexitat de temps mitjà: En el cas mitjà, agafeu totes les entrades aleatòries i calculeu el temps de càlcul per a totes les entrades.
I després ho dividim pel nombre total d'entrades. - La pitjor complexitat del temps: Definiu l'entrada per a la qual l'algorisme triga molt de temps o el temps màxim. En el pitjor, calculeu el límit superior d'un algorisme. Exemple: a la cerca lineal, quan hi ha dades de cerca a l'última ubicació de dades grans, es produeix el pitjor cas.
A continuació es mostra un full de revisió ràpida que podeu consultar a l'últim moment:
| Algorisme | Complexitat temporal | Complexitat espacial | ||
|---|---|---|---|---|
| El millor | Mitjana | El pitjor | El pitjor | |
| Ordenació de la selecció | O (n2) | O (n2) | O (n2) | O(1) |
| Classificació de bombolles | O(n) | O (n2) | O (n2) | O(1) |
| Ordenació d'inserció | O(n) | O (n2) | O (n2) | O(1) |
| Ordenació de pila | O(n log(n)) | O(n log(n)) | O(n log(n)) | O(1) |
| Classificació ràpida | O(n log(n)) | O(n log(n)) | O (n2) | O(n) |
| Fusionar Ordenar | O(n log(n)) | O(n log(n)) | O(n log(n)) | O(n) |
| Classificació de cubs | O (n + k) | O (n + k) | O (n2) | O(n) |
| Radix Sort | O(nk) | O(nk) | O(nk) | O(n + k) |
| Comte Ordenar | O (n + k) | O (n + k) | O (n + k) | fletxa) |
| Classificació de Shell | O(n log(n)) | O(n log(n)) | O (n2) | O(1) |
| Tim Sort | O(n) | O(n log(n)) | O(nlog(n)) | O(n) |
| Classificació d'arbres | O(n log(n)) | O(n log(n)) | O (n2) | O(n) |
| Ordenació de cubs | O(n) | O(n log(n)) | O(n log(n)) | O(n) |
A més, vegeu:
- Cercar i ordenar articles
- Preguntes GATE de l'any anterior sobre l'ordenació
- Temps i espai Complexitat de la classificació d'inserció
- Temps i espai Complexitat de l'ordenació de la selecció
- Complexitat temporal i espacial de l'ordenació de bombolles
- Complexitat de temps i espai d'ordenació ràpida
- Complexitat temporal i espacial de l'ordenació de fusió
- Complexitat temporal i espacial de l'algoritme d'ordenació de Radix