Асимптотичний аналіз

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

В математичному аналізі асимптотичний аналіз — це метод опису граничної поведінки. Дана методологія має багато застосувань в природничих науках. Наприклад

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

Найпростіший приклад, розгляд функції f(n), при описі її властивостей, коли n стає занадто великим. Таким чином, якщо f(n)=n2+3n, елемент 3n стає незначним в порівнянні з n2, при занадто великих n. Тоді кажуть, що функція f(n) є асимптотично еквівалентна n2 при n → ∞ й символічно записують як f(n) ~ n2.

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

Формально, для заданих двох комплекснозначних функцій f і g, що залежать від натурального аргументу n, пишемо

щоб позначити цей факт в термінах о-маленького, то

при

що еквівалентно

при

Це означає, що для довільної додатньої константи ε знайдеться така константа N, що

для всіх .

Якщо функція g(n) не рівна нулю (інакше границя записана нижче буде невизначеною), це твердження еквівалентне

Це відношення є відношення еквівалентності на множині функцій від n. Клас еквівалентності f загалом складається з усіх функцій g, котрі рівні f, в граничному сенсі.

Асимптотичний розклад[ред.ред. код]

Асимптотичний розклад функції f(x) фактично це представлення цієї функції у вигляді рядів, часткові суми яких не обов'язково збігаються, але такі що будь-які часткові суми являють собою асимптотичні формули для f.