Об’єднуємо всі разом

Повернемося знову до підрахунку кількості людей в кімнаті Припустимо, що можна вважати по одній людині за секунду Отже, якщо в кімнаті знаходиться 7 осіб, то підрахунок займають 7 секунд Очевидно, що якщо буде n людина, то підрахунок всіх займають n секунд Тому можна сказати, що цей алгоритм масштабується, як О (n) Що якщо завдання буде полягати в тому, щоб станцювати перед усіма, хто перебуває в кімнаті Оскільки, незалежно від того, скільки людина буде в кімнаті, це займе одне і той же час, значить, цей алгоритм масштабується, як O (1) У табл В1 показані інші часто зустрічаються характеристики складності

Таблиця В1 Значення масштабованості алгоритмів в часі

O (g (x)) Назва

1 log(n) n

n2

n3

2n

n

Постійна (відмінна масштабованість) Логарифмічна

Лінійна Квадратична Кубічна

Показова, або експоненціальна (погано)

Факторіал (дуже погано)

Як масштабується алгоритм подання всіх людей в кімнаті один одному Яка функція може промоделювати цей алгоритм Для представлення однієї людини необхідно 30 секунд, скільки часу займе уявлення 10 осіб один одному Що буде у разі 100 людина

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

*

*