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

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

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

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

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

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

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

f \sim g \quad (\text{as } n\to\infty)

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

f(n) = g(n) + o(g(n))\quad( при n\to\infty),\,

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

f(n) = (1+o(1))g(n)\quad( при n\to\infty).

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

|f(n)-g(n)|\leq\epsilon|g(n)| для всіх n\geq N~.

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

\lim_{n\to\infty} \frac{f(n)}{g(n)} = 1.

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

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

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