Книга: Разработка ядра Linux
Объединяем все вместе
Объединяем все вместе
Вернемся снова к подсчету количества людей в комнате. Допустим, что можно считать по одному человеку за секунду. Следовательно, если в комнате находится 7 человек, то подсчет займет 7 секунд. Очевидно, что если будет n человек, то подсчет всех займет n секунд. Поэтому можно сказать, что этот алгоритм масштабируется, как O(n). Что если задача будет состоять в том, чтобы станцевать перед всеми, кто находится в комнате? Поскольку, независимо от того, сколько человек будет в комнате, это займет одно и то же время, значит, этот алгоритм масштабируется, как O(1). В табл. В.1 показаны другие часто встречающиеся характеристики сложности.
Таблица В.1. Значения масштабируемости алгоритмов во времени
O(g(x)) | Название |
1 | Постоянная (отличная масштабируемость) |
log(n) | Логарифмическая |
n | Линейная |
n? | Квадратичная |
n? | Кубическая |
2? | Показательная, или экспоненциальная (плохо) |
n! | Факториал (очень плохо) |
Как масштабируется алгоритм представления всех людей в комнате друг другу? Какая функция может промоделировать этот алгоритм? Для представления одного человека необходимо 30 секунд, сколько времени займет представление 10 человек друг другу? Что будет в случае 100 человек?
- Объединяем все вместе – выработка требований
- Объединяем все вместе: культура Sony, двигающая рынок
- Профессиональная терминология не всегда уместна
- 2. Визуальный язык знают все Жест с ручкой в руках
- Домашняя мастерская: вы всегда на работе
- Программируя Вселенную. Квантовый компьютер и будущее науки
- Часть I Собственно компьютер и периферия Ху из ху и как все это совмещается и работает
- Повсеместная датификация
- Глава 10 Повседневная работа
- Почему при включении клавиатура не работает, а после загрузки Windows все нормально?
- Можно ли сделать так, чтобы вместе с часами отображалась и дата?
- Как разобраться в меню Пуск? Все так запутанно…