Ім'я файлу: Pyvovar.docx
Розширення: docx
Розмір: 18кб.
Дата: 08.05.2020
скачати
Пов'язані файли:
Лекція 9.docx
Розширення: docx
Розмір: 18кб.
Дата: 08.05.2020
скачати
Пов'язані файли:
Лекція 9.docx
O.M. Pyvovar
Research supervisor: A.L.Tarhonskiy,
Candidate of Physical and Mathematical Sciences, Associate professor
Zhytomyr Ivan Franko State University
Language tutor: PhD, Associate Professor Kuznyetsova A.V.
BIG O NOTATION AS ONE OF LANDAU’S SYMBOL
This paper deals with Landau’s concept of symbols and its application in modern programming which is also widely known in mathematics.
Big O notation (with a capital letter O), also called Landau's symbol, is a symbol used in complexity theory, computer science, and mathematics to describe the asymptotic behavior of functions. Basically, the concept shows how fast a function grows or declines. Landau's symbol comes from the name of a German mathematician Edmund Landau who popularized the notation.
The letter O is used because the rate of growth of a function is also called its order. For example, while analyzing some algorithm, one might find that the time (or the number of steps) necessary to perform the task of size n is given as
T(n)=4n2-2n+2. If the constants are ignored (which makes sense because these depend on the particular hardware the program is run on) and slower growing conditions, we can say "T(n) grows in the order of n2 " and write: T(n) = O(n2).
In mathematics, it is often important to get an interpretation of the approximation error. For instance, people will write eх = 1 + x + x2/2 + O(x3) for
x ->0to express the fact that the error is smaller in absolute value than some constants x3 if x is close enough to 0.
For the formal definition, suppose f(x) and g(x) are two functions defined on some subset of the real numbers. We write f(x) = O(g(x)) (or f(x) = O(g(x)) for x -> ∞ to be more precise) only on condition that constants N and C exist such that
|f(x)| ≤C|g(x)| for all x>N. Intuitively, this means that f does not grow faster than g.
If a is some real number, we write f(x) = O(g(x)) for x -> ain this case and only if there exist constants d > 0 and C such that |f(x)| ≤C |g(x)| for all x with
|x-a| < d.
This definition is the only one used in computer science (where typically only positive (additive) functions with a natural number n as an argument are considered; the absolute values can be ignored), while both applications appear in mathematics. The classes of the functions which are often used in algorithm analysis are listed below beginning with the slowly rising function.
The slower growing functions are listed first. С is some arbitrary constant.
| Notation | Name |
| O(1) | Constant |
| O(log(n)) | Logarithmic |
| O((log(n))c) | polylogarithmic |
| O(n) | Linear |
| O(n2) | Quadratic |
| O(nc) | Polynomial |
| O(cn) | Exponential |
The big O notation described here are very useful. They are used for approximating formulas for analysis of algorithms, and for the definitions of terms in polynomial. Being used mostly in computer sciences nowadays, basic Landau symbols may be more widely applied in the future.
References
Грин Д., Кнут Д. Математические методы анализа алгоритмов. — Перевод с англ. — М.: Мир, 1987. — 120 с.
Дж. Макконелл. Основы современных алгоритмов. — Изд. 2 доп. — М.: Техносфера, 2004. — 368 с.
Джон Э. Сэвидж. Сложность вычислений. — М.: Факториал, 1998. — 368 с.
Н. Крупский. Введение в сложность вычислений. — М.: Факториал Пресс, 2006. — 128 с.