racunanje logaritamske brzine algoritma

na nekoliko mesta sam naisao na to da se brzina algoritma izrazava preko log(n).....
da li neko zna nesto vise o tome?
(posebno, ako ima neki sajt gde je to lepo objasnjeno , to bi bilo odlicno)

hvala unapred.

pazi , nisi lepo to razumeo.To O(log(n)) ti predstavlja slozenost algoritma.Npr. kod binarnog pretrazivanja ti traba log(n) rekurzija da bi dosao do prave vrednosti.Znaci tim log(n) mnozis broj operacija koje se izvrsavaju u svakom ponavnjanju i tako dobijas ukupan broj operacija i samim tim priblizno vreme izvrsavanja.Pogledaj kako radi binarno pretrazivanje (Binary Search) pa ces shvatiti sta je to O(logn).
poz.

---

Izvadok od "Algorihms" od Sedgewick:

The first step in getting a rough estimate of the running time of a program
is to identify the inner loop. Which instructions in the program are executed
most often? Generally, it is only a few instructions, nested deep within the
control structure of a program, that absorb all of the machine cycles. It is
always worthwhile for the programmer to be aware of the inner loop, just to
be sure that unnecessary expensive instructions are not put there.
Second, some analysis is necessary to estimate how many times the inner
loop is iterated. It would be beyond the scope of this book to describe the
mathematical mechanisms which are used in such analyses, but fortunately
the running times many programs fall into one of a few distinct classes. When
possible, we’ll give a rough description of the analysis of the programs, but it
will often be necessary merely to refer to the literature. (Specific references
are given at the end of each major section of the book.) For example, the
results of a sophisticated mathematical argument show that the number of
recursive steps in Euclid’s algorithm when u is chosen at random less than v is
approximately ((12 In 2)/7r2) 1n TJ. Often, the results of a mathematical analysis
are not exact, but approximate in a precise technical sense: the result might
be an expression consisting of a sequence of decreasing terms. Just as we are
most concerned with the inner loop of a program, we are most concerned with
the leading term (the largest term) of a mathematical expression.
As mentioned above, most algorithms have a primary parameter N,
usually the number of data items to be processed, which affects the running
time most significantly. The parameter N might be the degree of a polynomial,
the size of a file to be sorted or searched, the number of nodes in a
graph, etc. Virtually all of the algorithms in this book have running time
proportional to one of the following functions:


1
Most instructions of most programs are executed once or at most
only a few times. If all the instructions of a program have this
property, we say that its running time is constant. This is obviously
the situation to strive for in algorithm design.

log N
When the running time of a program is logarithmic, the program
gets slightly slower as N grows.This running time commonly occurs
in programs which solve a big problem by transforming it into a
smaller problem by cutting the size by some constant fraction. For
our range of interest, the running time can be considered to be less
than a Yarge” constant. The base of the logarithm changes the
constant, but not by much: when N is a thousand, log N is 3 if the
base is 10, 10 if the base is 2; when N is a million, 1ogN is twice
as great. Whenever N doubles, log N increases by a constant, but
log N doesn’t double until N increases to N2.

N
When the running time of a program is linear, it generally is the case
that a small amount of processing is done on each input element.
When N is a million, then so is the running time. Whenever N
doubles, then so does the running time. This is the optimal situation
for an algorithm that must process N inputs (or produce N outputs).

NlogN
This running time arises in algorithms which solve a problem by
breaking it up into smaller subpr’oblems, solving them independently,
and then combining the solutions. For lack of a better adjective
(linearithmic?), we’ll say that th’e running time of such an algorithm
is “N log N.” When N is a million, N log N is perhaps twenty
million. When N doubles, the running time more than doubles (but
not much more).

N^2
When the running time of an algorithm is quadratic, it is practical
for use only on relatively small problems. Quadratic running times
typically arise in algorithms which process all pairs of data items
(perhaps in a double nested loop). When N is a thousand, the
running time is a million. Whenever N doubles, the running time
increases fourfold.

N^3
Similarly, an algorithm which prlocesses triples of data items (perhaps
in a triple-nested loop) has a cubic running time and is practical for
use only on small problems. VVhen N is a hundred, the running
time is a million. Whenever N doubles, the running time increases
eightfold.

2^N
Few algorithms with exponential running time are likely to be appropriate
for practical use, though such algorithms arise naturally as
“brute-force” solutions to problems. When N is twenty, the running
time is a million. Whenever N doubles, the running time squares!


The running time of a particular prlogram is likely to be some constant
times one of these terms (the “leading term”) plus some smaller terms. The
values of the constant coefficient and the terms included depends on the results
of the analysis and on implementation details. Roughly, the coefficient of the
leading term has to do with the number of instructions in the inner loop:
at any level of algorithm design it’s prudent to limit the number of such
instructions. For large N the effect of the leading term dominates; for small
N or for carefully engineered algorithms, more terms may contribute and
comparisions of algorithms are more difficult. In most cases, we’ll simply refer
to the running time of programs as “linear,” “N log N, ” “cubic,” etc., with
the implicit understanding that more detailed analysis or empirical studies
must be done in cases where efficiency is very important.