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

нотація для запису асимтотичної поведінки функції

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

Приклад використання нотації О-велике: , бо існують (наприклад, ) та (наприклад, ), такі, що для кожного .

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

Відношення «O»Редагувати

Означення для функцій дійсного (комплексного) аргументу

Через   позначимо   або  . Нехай  ,   і   — гранична точка множини  . Через   позначимо  -окіл точки  .

Функція   називається підпорядкованою функції   при  , якщо існують дійсні додатні числа   та   такі, що для довільного   виконується нерівність  

Для   функція   називається підпорядкованою функції   при  , якщо існують дійсне додатнє число   і дійсне   такі, що для довільного   виконується нерівність  

Для   функція   називається підпорядкованою функції   при  , якщо існують дійсне додатнє число   і дійсне   такі, що для довільного   виконується нерівність  

Позначення:  ,   або  ,  .

Означення для функцій цілого невід'ємного аргументу

Нехай  . Функція   називається підпорядкованою функції   якщо існують додатнє дійсне число   і натуральне   такі, що для довільного   виконується нерівність  

Позначення:   або  .

Також кажуть, що «  зростає не швидше ніж  » або «  є асимптотичною верхньою оцінкою  ».

ВластивостіРедагувати

  1.   для довільного  
  2.   для довільного  
  3. Якщо  , то  
  4. Якщо   і  , то  
  5. Якщо   то  
  6. Якщо   і   то  
  7. Якщо   і   то  
  8. Якщо   і   то   (транзитивність)

Відношення «Ω»Редагувати

Означення для функцій дійсного (комплексного) аргументу

Через   позначимо   або  . Нехай  ,   і   — гранична точка множини  . Через   позначимо  -окіл точки  .

Кажуть, що функція   підпорядковує функцію   при  , якщо існують дійсні додатні числа   та   такі, що для довільного   виконується нерівність  

Для   кажуть, що функція   підпорядковує функцію   при  , якщо існують дійсне додатнє число   і дійсне   такі, що для довільного   виконується нерівність  

Для   кажуть, що функція   підпорядковує функцію   при  , якщо існують дійсне додатнє число   і дійсне   такі, що для довільного   виконується нерівність  

Позначення:  ,   або  ,  .

Означення для функцій цілого невід'ємного аргументу

Нехай  . Кажуть, що функція   підпорядковує функцію   якщо існують додатнє дійсне число   і натуральне   такі, що для довільного   виконується нерівність  

Позначення:   або  .

Також кажуть, що «  зростає не повільніше ніж  » або «  є асимптотичною нижньою оцінкою  ».

ВластивостіРедагувати

  1.   тоді й лише тоді, коли  
  2.   для довільного  
  3.   для довільного  
  4. Якщо  , то  
  5. Якщо   і  , то  
  6. Якщо   то  
  7. Якщо   і   то  
  8. Якщо   і   то  
  9. Якщо   і   то   (транзитивність)

Відношення «Θ»Редагувати

Означення для функцій дійсного (комплексного) аргументу

Через   позначимо   або  . Нехай  ,   і   — гранична точка множини  . Через   позначимо  -окіл точки  .

Функція   називається асимптотичною точною оцінкою функції   при  , якщо існують дійсні додатні числа     та   такі, що для довільного   виконується нерівність  

Для   функція   називається асимптотичною точною оцінкою функції   при  , якщо існують дійсні додатні числа     і дійсне   такі, що для довільного   виконується нерівність  

Для   функція   називається асимптотичною точною оцінкою функції   при  , якщо існують дійсні додатні числа     і дійсне   такі, що для довільного   виконується нерівність  

Позначення:  ,   або  ,  .

Означення для функцій цілого невід'ємного аргументу

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

Позначення:   або  .

ВластивостіРедагувати

  1.   тоді й лише тоді, коли   і  
  2.   тоді й лише тоді, коли  

Відношення «o»Редагувати

Означення для функцій дійсного (комплексного) аргументу

Через   позначимо   або  . Нехай  ,   і   — гранична точка множини  . Через   позначимо  -окіл точки  .

Функція   називається знехтуваною у порівнянні з функцією   при   якщо для довільного додатнього   існує додатнє   таке, що для довільного   виконується нерівність  

Для   функція   називається знехтуваною у порівнянні з функцією   при  , якщо для довільного додатнього   існує додатнє   таке, що для довільного   виконується нерівність  

Для   функція   називається знехтуваною у порівнянні з функцією   при  , якщо для довільного додатнього   існує додатнє   таке, що для довільного   виконується нерівність  

Позначення:   або  

Означення для функцій цілого невід'ємного аргументу

Нехай  . Функція   називається знехтуваною у порівнянні з функцією  , якщо для довільного додатнього   існує натуральне   таке, що для довільного   виконується нерівність  

ВластивостіРедагувати

  1.   тоді й лише тоді, коли  
  2. Якщо   то  
  3. Якщо   і   то   Таким чином,   Аналогічно  
  4. Якщо   і   то  
  5. Якщо   і   то  
  6. Якщо   і   то   (транзитивність)

Відношення «ω»Редагувати

Означення для функцій дійсного (комплексного) аргументу

Через   позначимо   або  . Нехай  ,   і   — гранична точка множини  . Через   позначимо  -окіл точки  .

Функція   називається домінуючою у порівнянні з функцією   при   якщо для довільного додатнього   існує додатнє   таке, що для довільного   виконується нерівність  

Для   функція   називається домінуючою у порівнянні з функцією   при  , якщо для довільного додатнього   існує додатнє   таке, що для довільного   виконується нерівність  

Для   функція   називається домінуючою у порівнянні з функцією   при  , якщо для довільного додатнього   існує додатнє   таке, що для довільного   виконується нерівність  

Позначення:   або  

Означення для функцій цілого невід'ємного аргументу

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

ВластивостіРедагувати

  1.   тоді й лише тоді, коли  
  2.   тоді й лише тоді, коли  
  3. Якщо   то  
  4. Якщо   і   то   Таким чином,   Аналогічно  
  5. Якщо   і   то  
  6. Якщо   і   то  
  7. Якщо   і   то   (транзитивність)

Відношення еквівалентності функційРедагувати

Через   позначимо   або  . Нехай  ,   і   — гранична точка множини  .

Функції   і   називаються еквівалентними при   якщо  

Означення для функцій цілого невід'ємного аргументу аналогічне.

Позначення:   або  

ВластивостіРедагувати

  1. Відношення   є відношенням еквівалентності на множині функцій.
  2. Нехай для всіх     Тоді   тоді й лише тоді, коли  
  3. Якщо   і   то  
  4. Нехай для всіх    ,   і   Тоді для будь-якої функції   з існування однієї з границь
 ,  
випливає існування другої границі і їх рівність.
Аналогічно з існування однієї з границь
 ,  
випливає існування другої і їх рівність.

ПрикладиРедагувати

Приклад 1: Нехай  ,   і  . Маємо:

 

тобто   і ця нерівність виконується для всіх  

Звідси  

 , тут   і   Звідси  

Отже,  

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

 

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

 

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

ВикористанняРедагувати

Нотація Ландау має дві основні сфери використання:

В обох випадках функція   в позначеннях, як правило, вибирається максимально простою без константних множників.

Деякі важливі класи відношеньРедагувати

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

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

Нотація Назва Приклад
  сталий час Визначенно парності числа (у двійковому запису); Пошук у хеш-таблиці
  двічі логарифмічний Час амортизації на одну операцію при використанні обмеженої черги з пріоритетом[1]
  логарифмічний час Двійковий пошук; Швидке піднесення до степеня
 
 
полілогарифмічний час
  лінійний час Пошук найбільшого або найменшого елементу невпорядкованого масиву
  лінеаритмічний час Швидке сортування; Сортування злиттям
  квадратичний час Сортування бульбашкою; Сортування включенням
  поліноміальний час Алгоритм Кармаркара[en] для лінійного програмування; Тест простоти AKS
 
 
експоненціальний час Вирішення задачі комівояжера за допомогою динамічного програмування
  факторіальний час Вирішення задачі комівояжера повним перебором

Розширення нотації ЛандауРедагувати

У інформатиці іноді використовується позначення Õ (читається як м’яке О): f(n) = Õ(g(n)) це скороченням до f(n) = O(g(n) logk n) для деякого k.[2] Іноді для цього використовують O*.[3] По суті, це нотація великого O, яка ігнорує логарифмічні множники, оскільки на швидкість зростання деякі більші функції від великих вхідних параметрів впливають значно більше, що важливіше для прогнозування поганої продуктивності під час виконання. Це позначення часто використовується, щоб уникнути «придирок» до темпів зростання, які вважаються жорстко обмеженими (logk n завжди є o(nε) для будь-якої константи k і будь-якого ε > 0).

Для позначення функцій, які мають час зростання між поліноміальним та експоненціальним, використовують L-нотацію[en]:

 

де   — додатня стала,  

Узагальнення для функцій багатьох зміннихРедагувати

Існує декілька узагальнень нотації Ландау для функцій багатьох функцій.[4][5] Одне з них:

Для функції  , де  , позначимо

  для всіх  

Нехай  . Функція   називається підпорядкованою функції   якщо існують додатнє дійсне число   і натуральне   такі, що для всіх   виконуються нерівності

 

та

 

Позначення:   або  .

Аналогічно,  , якщо існують додатнє дійсне число   і натуральне   такі, що для всіх   виконуються нерівності

 

та

 

 , якщо існують додатні дійсні числа  ,   і натуральне число   такі, що для всіх   виконуються нерівності

 

та

 

Для функцій одного аргументу матимемо, що для   при деякому   буде  ,   і   Однак, для   при всіх   це не буде вірним.


 , якщо для кожного додатного дійсного числа   існує натуральне число   таке, що для всіх   виконуються нерівності

 

та

 

 , якщо для кожного додатного дійсного числа   існує натуральне число   таке, що для всіх   виконуються нерівності

 

та

 

Для функцій однієї змінної відношення  ,   збігаються з відношеннями  ,   відповідно.

Додаткова умова до   і   дозволяє зберегти деякі корисні властивості.

ВластивостіРедагувати

  1. Для довільного   буде  
  2. Якщо   і   то  
  3. Якщо   не спадає по всім аргументам і   при   для деякого   то з того, що   випливає, що  
  4. Якщо   та   не спадають по всім аргументам, то з того, що   та   випливає, що  

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

ЛітератураРедагувати

ПриміткиРедагувати

  1. Mehlhorn, Kurt; Naher, Stefan (1990). Bounded ordered dictionaries in O(log log N) time and O(n) space. Information Processing Letters 35 (4): 183–189. doi:10.1016/0020-0190(90)90022-P. 
  2. Introduction to algorithms. Cormen, Thomas H. (вид. Third). Cambridge, Mass.: MIT Press. 2009. с. 63. ISBN 978-0-262-27083-0. OCLC 676697295. 
  3. Andreas Björklund and Thore Husfeldt and Mikko Koivisto (2009). Set partitioning via inclusion-exclusion. SIAM Journal on Computing 39 (2): 546–563.  Див. розділ 2.3, с.551.
  4. Howell, Rodney (2008). On Asymptotic Notation with Multiple Variables. 
  5. Guéneau, Armaël; Charguéraud, Arthur; François, Pottier (2018). A Fistful of Dollars: Formalizing Asymptotic Complexity Claims via Deductive Program Verification.