Безліч більшого-тета

Коли говорять про позначення великого-О, то найчастіше мають на увазі те, що Дональд Кнут (Donald Knulh) описував за допомогою позначення великого-тета. Позначення болипой-О відповідає верхній межі Наприклад, число 7 – це верхня межа числа 6, крім того, числа 9, 12 і 65 – це теж верхні межі числа 6 Коли розглядають зростання функції, то зазвичай найбільш цікава найменша верхня межа або функція, яка моделює як верхню, так і нижню межу . Профессо р Кнут описує це за допомогою позначення великого-тета таким чином

Якщо f (х) належить безлічі великого-тета від g (x), то g (х) являетс я одночасно і верхньою і нижньою межею f (х)

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

Отже, коли говорять про позначення великого-О, то найчастіше мають на увазі найменший можливий варіант великого-О – Болиное-тета. Про це не потрібно особливо хвилюватися, якщо, звичайно, немає бажання принести задоволення професору Кнуту

1 Якщо цікаво, т о нижня я кордонів а опісиваетс я з допомогу ю обозначени я великого-омега Певні е аналогічними про определени ю безлічі великого-О, за винятком того, чт про значени я функції g (s) повинні побут ь менше значень функції f (х) чи рівні їм

Джерело: Лав, Роберт Розробка ядра 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>

*

*