Siç është përmendur në përgjigjen e pyetjes së lidhur, një mënyrë e zakonshme që një algoritëm të ketë kompleksitet kohor O(log n) është që ai algoritëm të punon duke shkurtuar në mënyrë të përsëritur madhësinë e hyrjes poshtë nga ndonjë faktor konstant në çdo përsëritje.
Cili është kuptimi i log n?
O(log N) në thelb do të thotë koha rritet në mënyrë lineare ndërsa n rritet në mënyrë eksponenciale. Pra, nëse duhen 1 sekondë për të llogaritur 10 elementë, do të duhen 2 sekonda për të llogaritur 100 elementë, 3 sekonda për të llogaritur 1000 elementë, e kështu me radhë. Është O(log n) kur ne bëjmë llojin e algoritmeve të ndarë dhe të pushtuar, p.sh. kërkimi binar.
Çfarë është O dhe log n?
Për hyrjen e madhësisë n, një algoritëm i O(n) do të kryejë hapa proporcional me n, ndërsa një algoritëm tjetër i O(log(n)) do të kryejë hapa përafërsisht log(n). Është e qartë se log(n) është më i vogël se n prandaj algoritmi i kompleksitetit O(log(n)) është më i mirë.
Si e llogaritni log n?
Ideja është që një algoritëm është O(log n) nëse në vend që të lëvizni nëpër një strukturë 1 me 1, e ndani strukturën në gjysmë vazhdimisht dhe bëni një numër konstant operacionesh për çdo ndarje. Algoritmet e kërkimit ku hapësira e përgjigjeve vazhdon të ndahet janë O(log n).
Çfarë është log n Square?
Log ^2 (
) do të thotë se është në proporcion me log të log për një problem të madhësisë
. Regjistri(
)^ 2 do të thotë se ështëproporcionale me katrorin të log.
