Главная » Ядро Linux » Объединяем все вместе

0

Вернемся снова  к  подсчету   количества людей  в  комнате.  Допустим,  что  можно считать  по  одному  человеку за  секунду.   Следовательно, если  в  комнате  находится  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 с. : ил. — Парал. тит. англ.

По теме:

  • Комментарии