Hovedinnhold
Kurs: (Informatikk > Enhet 1
Leksjon 3: Asymptotisk notasjonFunksjoner med asymptotisk notasjon
When we use asymptotic notation to express the rate of growth of an algorithm's running time in terms of the input size , it's good to bear a few things in mind.
Let's start with something easy. Suppose that an algorithm took a constant amount of time, regardless of the input size. For example, if you were given an array that is already sorted into increasing order and you had to find the minimum element, it would take constant time, since the minimum element must be at index 0. Since we like to use a function of in asymptotic notation, you could say that this algorithm runs in time. Hvorfor? Because , and the algorithm's running time is within some constant factor of 1. In practice, we don't write , however; we write .
Now suppose an algorithm took time. You could also say that it took time. Whenever the base of the logarithm is a constant, it doesn't matter what base we use in asymptotic notation. Why not? Because there's a mathematical formula that says
for all positive numbers , , and . Therefore, if and are constants, then and differ only by a factor of , and that's a constant factor which we can ignore in asymptotic notation.
Therefore, we can say that the worst-case running time of binary search is for any positive constant . Why? The number of guesses is at most , generating and testing each guess takes constant time, and setting up and returning take constant time. However, as a matter of practice, we often write that binary search takes time because computer scientists like to think in powers of 2.
There is an order to the functions that we often see when we analyze algorithms using asymptotic notation. If and are constants and , then a running time of grows more slowly than a running time of . For example, a running time of , which is , grows more slowly than a running time of . The exponents don't have to be integers, either. For example, a running time of grows more slowly than a running time of , which is .
The following graph compares the growth of , , and :
Logarithms grow more slowly than polynomials. That is, grows more slowly than for any positive constant . But since the value of increases as increases, grows faster than .
The following graph compares the growth of , , and :
Here's a list of functions in asymptotic notation that we often encounter when analyzing algorithms, ordered by slowest to fastest growing:
Note that an exponential function , where , grows faster than any polynomial function , where is any constant.
The list above is not exhaustive, there are many functions with running times not listed there. You'll hopefully run into a few of those in your computer science journey.
This content is a collaboration of Dartmouth Computer Science professors Thomas Cormen and Devin Balkcom, plus the Khan Academy computing curriculum team. The content is licensed CC-BY-NC-SA.
Ønsker du å delta i samtalen?
Ingen innlegg enda.