Безліч Про

Корисним позначенням асимптотичної поведінки функції є верхня межа – функція, значення якої завжди більше значень досліджуваної функції Кажуть, що верхня межа деякої функції зростає швидше, ніж розглянута функція Спеціальне позначення великого-О використовується для опису цього зростання Це записується як f (х)О (g (х}) і читається так: f належить безлічі О-болипой від g Формальне математичне визначення має наступний вигляд

Е з л і f (x) п р і н а д л і ж и т м н о ж е с т в у б о л ь ш о г о O (g (х)), т о

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

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

Джерело: Лав, Роберт Розробка ядра Linux, 2-е видання : Пер з англ – М: ТОВ «ІД Вільямс »2006 – 448 с : Ил – Парал тит англ

Схожі статті:


Сподобалася стаття? Ви можете залишити відгук або підписатися на RSS , щоб автоматично отримувати інформацію про нові статтях.

Коментарів поки що немає.

Ваш отзыв

Поділ на параграфи відбувається автоматично, адреса електронної пошти ніколи не буде опублікований, допустимий HTML: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

*

*