Ką tiksliai reiškia O(log n)?

Aš mokausi apie "Big O" užrašo veikimo laikus ir amortizuotus laikus. Suprantu O(n) tiesinio laiko sąvoką, kuri reiškia, kad įvesties dydis proporcingai įtakoja algoritmo augimą... tas pats pasakytina ir apie, pavyzdžiui, kvadratinį laiką O(n2) ir t. t. Netgi apie algoritmus, tokius kaip permutacijų generatoriai, kurių O(n!) laikas auga faktorialais.

Pavyzdžiui, ši funkcija yra O(n), nes algoritmas auga proporcingai įėjimui n:

f(int n) {
  int i;
  for (i = 0; i < n; ++i)
    printf("%d", i);
}

Panašiai, jei būtų įterptas ciklas, laikas būtų O(n2).

Tačiau kas tiksliai yra O(log n)? Pavyzdžiui, ką reiškia teiginys, kad pilno dvejetainio medžio aukštis yra O(log n)?

Žinau (gal ir nelabai išsamiai), kas yra logaritmas, ta prasme, kad: log10 100 = 2, bet negaliu suprasti, kaip sutapatinti funkciją su logaritminiu laiku.

Flimzy
Redaguotas klausimas priešpietr liepa 2019 в 8:29
Programavimas
time-complexity big-o
popietr vasaris 2010 в 8:05
27 peržiūros

Logaritminis veikimo laikas (O(log n)) iš esmės reiškia, kad veikimo laikas auga proporcingai įvesties dydžio logaritmui - pavyzdžiui, jei 10 elementų užima ne daugiau kaip x laiko, 100 elementų - ne daugiau kaip 2x, o 10 000 elementų - ne daugiau kaip 4x, tai atrodo, kad sudėtingumas yra O(log n).

Anon.
Redaguotas atsakymas popietr vasaris 2010 в 8:27
Komentarai (10)

Tai paprasčiausiai reiškia, kad laikas, reikalingas šiai užduočiai atlikti, auga su log(n) (pavyzdys: 2 s, kai n = 10, 4 s, kai n = 100, ...). Daugiau tikslumo rasite Vikipedijos straipsniuose Dvejetainės paieškos algoritmas ir Big O notacija.

Komentarai (0)

Pilnas dvejetainis pavyzdys yra O(ln n), nes paieška atrodo taip:

1 2 3 4 5 6 7 8 9 10 11 12

Ieškant 4, gaunami 3 atitikmenys: 6, 3, tada 4. Ir log2 12 = 3, o tai yra geras apytikslis rodiklis, rodantis, kiek reikėjo paieškų.

Komentarai (2)