Kaip rašoma algoritminė sudėtingumas? Kokia yra burbulo rūšiavimo sudėtingumas? Kokia yra greito rūšiavimo sudėtingumas?

Algoritminė sudėtingumas paprastai rašomas Big O notacijoje, kuri apibūdina asimptotinį algoritmo vykdymo laiko arba atminties naudojimo įvertinimą priklausomai nuo įvesties duomenų dydžio.

• Burbulinis rūšiavimas turi sudėtingumą O(n²) blogiausiu ir vidutiniu atveju, nes kiekvienas elementas lyginamas su kiekvienu kitu.

• Greitasis rūšiavimas vidutiniškai veikia O(n log n), tačiau blogiausiu atveju (pavyzdžiui, kai masyvas jau yra surūšiuotas ir pasirenkamas blogas pivotas) gali sumažėti iki O(n²).

Pavyzdys įrašo:

Burbulinis rūšiavimas: O(n^2)
Greitasis rūšiavimas: O(n log n) vidutiniškai, O(n^2) blogiausiu atveju