Ko tieši nozīmē O(log n)?

Es mācos par Big O notācijas darbības laikiem un amortizētiem laikiem. Es saprotu jēdzienu O(n) lineārais laiks, kas nozīmē, ka ievades lielums proporcionāli ietekmē algoritma pieaugumu... un tas pats attiecas, piemēram, uz kvadrātisko laiku O(n2) utt... pat uz algoritmiem, piemēram, permutāciju ģeneratoriem, ar O(n!) laikiem, kas pieaug ar faktoriāliem.

Piemēram, šāda funkcija ir O(n), jo algoritms aug proporcionāli ievades n:

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

Līdzīgi, ja būtu ielikta cilpa, laiks būtu O(n2).

Bet kas tieši ir O(log n)? Piemēram, ko nozīmē teikt, ka pilnīga bināra koka augstums ir O(log n)?

Es zinu (varbūt ne pārāk detalizēti), kas ir logaritms tādā nozīmē, ka: log10 100 = 2, bet es nevaru saprast, kā identificēt funkciju ar logaritmisko laiku.

Flimzy
Rediģēts jautājums 15priekšpusdienari0t jūlijā 2019 в 8:29
Programmēšana
time-complexity big-o
21pēcpusdienari6t februārī 2010 в 8:05
140 skati

Logaritmiskais darbības laiks (O(log n)) būtībā nozīmē, ka darbības laiks pieaug proporcionāli ievades lieluma logaritmam - piemēram, ja 10 vienībām nepieciešams ne vairāk kā x laika, 100 vienībām - ne vairāk kā 2x, bet 10 000 vienībām - ne vairāk kā 4x, tad tas izskatās pēc O(log n) laika sarežģītības.

Anon.
Rediģēta atbilde 21pēcpusdienari6t februārī 2010 в 8:27
Komentāri (10)

Tas vienkārši nozīmē, ka šim uzdevumam vajadzīgais laiks pieaug ar log(n) (piemērs: 2s, ja n = 10, 4s, ja n = 100, ...). Lai iegūtu precīzāku informāciju, izlasiet Vikipēdijas rakstus Binary Search Algorithm un Big O Notation.

Komentāri (0)

Pilns binārais piemērs ir O(ln n), jo meklēšana izskatās šādi:

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

Meklējot 4, iegūst 3 pozitīvos rezultātus: 6, 3, tad 4. Un log2 12 = 3, kas ir labs aptuvenais rādītājs tam, cik daudz trāpījumu ir vajadzīgi.

Komentāri (2)