Pentru a vă înregistra, vă rugăm să trimiteți un email către administratorul site-ului.
Pune o întrebare

3.6k intrebari

6.8k raspunsuri

15.5k comentarii

2.5k utilizatori

3 plusuri 0 minusuri
318 vizualizari
Sa spunem ca am de ordonat crescator un sir de n numere naturale. Care este metoda optima pentru a face asta, dpdv al timpului necesar (respectiv al complexitatii algoritmului matematic folosit)? Cate comparatii trebuie sa fac intre elementele componente ale sirului de numere?
Senior (8.1k puncte) in categoria Matematica

1 Raspuns

1 plus 0 minusuri
In C, algoritmii optimi de sortare sunt QuickSort, HeapSort si MergeSort, toate 3 cu colmplexitate minima posibila, O(n log n) in medie. Dintre astea 3, doar QuickSort poate avea complexitate mai mare de O(n log n) si anume O(n^2). Dar in medie e suficient de bun. Timpul depinde de mai multi factori, printre care procesorul calculatorului, datele de intrare, etc. Dar in cazul cel mai defavorabil, pe acelasi calculator, mereu un algoritm cu complexitate redusa va avea un timp mai bun de executare decat alt algoritm folosit tot pe cel mai defavirabil caz, dar cu complexitate mai mare, daca se introduce acelasi numar de numere.

Dar daca nu ai un numar mare de nr ce trebuie sortate, merge si BubbleSort, care e foarte usor de scris si nu necesita cod recursiv.
Novice (339 puncte)
...