Небезпека, пов’язана зі складністю алгоритмів

Очевидно, що буде розумним уникати алгоритмів, які масштабуються, як О (n) або О (2n) Більш того, заміна алгоритму, який масштабується, як О (n), алгоритмом, який масштабується, як O (1), – це зазвичай серйозне поліпшення Проте це не завжди так, і не можна приймати рішення наосліп, базуючись тільки на описі болипой-О. Згадайте, що у визначенні безлічі О (g (х)) фігурує константа, на яку множиться значення функції g (х) Тому є можливість, що алгоритм, який масштабується, як O (1), буде виконуватися протягом 3 годин Отже, він буде виконуватися завжди протягом 3 годин, незалежно від кількості вхідних даних, але це може виявитися довше, в порівнянні з алгоритмом, який масштабується, як О (n), пр і невеликій кількості вхідних даних При порівнянні алгоритмів необхідно завжди брати до уваги кількість вхідних даних Не варто сліпо оптимізувати для деякого випадково обраного варіанту

г

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

*

*