Kompleksiteti algoritmik i strukturave ne te cilat ruhen te dhenat informatike

Per pyetje si: Cfare jane strukturat e te dhenave? Cfare eshte nje algoritm? ju lutem te vizitoni blogun tim perseri sepse do vijojne artikuj reth ketyre temave.
Ky eshte nje artikull i avancuar i cili presupozon qe juve dini pergjigjen e pyetjeve te mesiperme.

Perpara se te kalojme te kompleksiteti algoritmik te flasim ne fillim per strukturat e te dhenave. Momentalisht jane mbi 100 struktura per te ruajtur te dhenat informatike, mud te gjeni nje liste ketu: https://en.wikipedia.org/wiki/List_of_data_structures ky artikull do fokusohet vetem te strukturat me te perdorura sic jane: Array, Stack, Queue, Singly-Linked List, Doubly-Linked List, Skip List, Hash Table, Binary Search Tree, Cartezian Tree, B-Tree, Red-Black Tree, Splay Tree, AVL Tree, KD Tree. Gjithashtu do flasim dhe per kompleksitetin algoritmit te shumices se algoritmave te radhitjes sic este:QuickSort, MergeSort, TimSort, Bubble Sort, Insertion Sort, Selection Sort, Tree Sort, Shell Sort, Bucket Sort, Radix Sort, Counting Sort, Cube Sort.

Do mbaj emerimet ne anglisht dhe do perkthej vetem atje ku me duket e arsyeshme, sepse sipas mendimit tim disa nga perkthimet e termave informatike ne shqip nuk tingellojne bukur, pervec kesaj me siguri do keni nevoje te kerkoni me shume informacione rreth strukturave te te dhenave, dhe ne anglisht do gjeni shume me shume informacione sesa ne shqip.

Ok, Cfare eshte kompleksiteti algoritmik?
Kompleksiteti algoritmik eshte nje menyre per te matur se sa eficient eshte nje algoritm. Ne informatike kemi dy lloj eficiencash: eficience kohore, eficience e hapsires ne memorje.
Eficienca kohore i referohet kohes qe i duhet nje algoritmi te mbaroje. Psh: Sa milisekona i duhet algoritmit te radhitjes QuickSort per te radhitur nje vektor me numra? 
Eficienca  e hapsires ne memorie i referohet hapsires  se zene ne memorien kompiuterike nga nje algoritim, nga fillimi deri ne mabrimin e tij. Psh: Sa te dhena duhet te ruaj ne memorje algoritmi QuickSort per te radhitur nje vektor me numra?

Ne qofte se studiojme me vemendje te dyja pyetjet e mesiperme, per secilen nga pyetjet na lind nje pyetje tjeter. Psh: per pyetjen "Sa milisekona i duhet algoritmit te radhitjes QuickSort per te radhitur nje vektor me numra?" lind pyetja "Sa numra ka vektori?" eshte e llogjikshme qe numri i milisekondave eshte i varur nga sa numra ka vektroi. 

Kompleksiteti algoritmik shenohet me O ("Big O notation" sic thuhet ne anglisht) dhe eshte nje funksion matematikor qe varet nga nje parameter, ky parameter sic mund ta paramendoni eshte numri i elementve qe hyn ne algoritm. Do e shenojme kete numer me shkronjen n
Gjate viteve informaticienet kane studiuar komplekistetet algoritmike te shume algoritmave dhe kane veryer se gjashte kompleksitete perseriten gjithmone, keto jane:

  1. O(1) - kompleksiteti konstant, ky kompleksitet nuk varet nga numri i elementeve qe hyjne ne algoritm. Algoritmi do mbaroje exekutimin ne nje kohe konstante.
  2. O(log n) - kompleksiteti logaritmik, algoritmi do mbaroje exekutimin ne nje kohe logaritmike
  3. O(n) - kompleksiteti liniar, algoritmi do mbaroje executimin ne nje kohe liniare.
  4. O(n log n)
  5. O(n^2)
  6. O(2^n)
  7. O(n!)

Ne figuren e meposhtme do gjeni nje grafik te mare nga websiti: http://bigocheatsheet.com/ ku tregohet secili kompleksitet. Verejme se algoritmat ne te djathe te grafikut qe jane te shenuar me ngjyre: jeshile, verdhe kane nje kompleksitet algoritmik me te mire se sa ata ne te majte qe jane me te kuqe. Psh nje algoritm qe ka kompleksitetin O(n!) nuk mund te vihet asnjer ne praktike sepse kerkon shume kohe per te mbaruar.

Me poshte keni nje tabel ne te cilin pershkruhen strukturat e te dhenave me te perdorura dhe kompleksiteti algoritmik i seciles strukture per operacionet e cakturara.

Me poshte keni nje tabel me kompleksitetin algoritmik te algoritmave te radhitjes.