Відкрити головне меню

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

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

Зміст

ОзначенняРедагувати

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

 

якщо існує константа 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!) факторіальне

Див. такожРедагувати