Нотація Ландау

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

Асимптотична нотація великого О, відома також як нотація Ландау — розповсюджена математична нотація для формального запису асимптотичної поведінки функцій. Широко вживається в теорії складності обчислень, інформатиці та математиці.

Названа нотацією Ландау на честь німецького математика Едмунда Ландау, який і популяризував цю нотацію.

Означення[ред.ред. код]

«О» велике. Нехай задані дві комплекснозначні функції та визначені в деякій множині комплексної площини. Тоді говорять, що

якщо існує константа K >0, що виконується нерівність |f(z)| ≤ K |g(z)| для .

«O» велике в околі . Нехай і дві комплекснозначні функції визначені в деякій множині комплексної площини, замикання якої містить точку (тобто, є граничною точкою ). Тоді ми пишемо

при з

якщо існує число таке, що

в сенсі означення «О» великого. Тобто, обмежена величиною добутку константи на для всіх з , які лежать досить близько до .

«O» велике в нескінченності. Нехай і дві комплекснозначні функції визначені в необмежиній множині комплексної площини. Тоді ми кажемо, що

при з

якщо існує число так що

,

в сенсі означення «О» великого. Тобто, обмежена величиною добутку деякої константи на , для достатньо великих з .

«o» маленьке. Нехай і дві комплекснозначні функції визначені в деякій множині комплексної площини замикання якої містить точку . Тоді ми кажемо, що

при з

якщо для довільного , як завгодно малого, існує відповідне йому , що

для і .

Тобто, є меншим за величиною за будь-який малий добуток для досить близьких до точки .

«о» маленьке в нескінченності Нехай і комплекснозначні функції визначені в необмеженій множині комплексної площини. Тоді ми пишемо

при з

якщо для довільного , як завгодно малого, ми можемо знайти відповідне таке що

для і .

Позначення[ред.ред. код]

Функції f(x) та g(x) називають функціями одного порядку, якщо f(x) = O(g(x)) та g(x) є O(f(x)) для x x0;

Часто для позначення того факту, що f(x) є O(g(x)) використовується запис f(x) = O(g(x)), хоч це не зовсім правильно і в деяких випадках може привести до плутанини.

Приклад[ред.ред. код]

Нехай і цілі числа. Якщо , то при . Для доведення цього запишемо

Покладемо . Тоді означає що , оскільки . Отже, якщо , нерівність виконується при виборі . Також, з аналогічним обмеженням на та , ми маємо, що при з . Для доведення цього запишемо

Виберемо, наприклад, . Тоді, означає, що оскільки .

Деякі важливі класи відношень[ред.ред. код]

Графіки деяких поширених функцій.

Нижче наведений список класів функцій, які часто зустрічаються в аналізі алгоритмів. Тут n ∞, с — константа. Функції, які зростають повільніше, наведені першими.

нотація назва
O(1) константа
O(log n) логарифмічне
O([log n]c) полілогарифмічне
O(n) лінійне
O(n · log n) лінеарітмічне
O(n2) квадратичне
O(nc) поліноміальне
O(cn) експоненціальне
O(n!) факторіальне

Див. також[ред.ред. код]


Сигма Це незавершена стаття з математики.
Ви можете допомогти проекту, виправивши або дописавши її.