Объединяем все вместе

Объединяем все вместе

Вернемся снова к подсчету количества людей в комнате. Допустим, что можно считать по одному человеку за секунду. Следовательно, если в комнате находится 7 человек, то подсчет займет 7 секунд. Очевидно, что если будет n человек, то подсчет всех займет n секунд. Поэтому можно сказать, что этот алгоритм масштабируется, как O(n). Что если задача будет состоять в том, чтобы станцевать перед всеми, кто находится в комнате? Поскольку, независимо от того, сколько человек будет в комнате, это займет одно и то же время, значит, этот алгоритм масштабируется, как O(1). В табл. В.1 показаны другие часто встречающиеся характеристики сложности.

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

O(g(x)) Название
1 Постоянная (отличная масштабируемость)
log(n) Логарифмическая
n Линейная
n? Квадратичная
n? Кубическая
2? Показательная, или экспоненциальная (плохо)
n! Факториал (очень плохо)

Как масштабируется алгоритм представления всех людей в комнате друг другу? Какая функция может промоделировать этот алгоритм? Для представления одного человека необходимо 30 секунд, сколько времени займет представление 10 человек друг другу? Что будет в случае 100 человек?

Поделитесь на страничке

Следующая глава >

Похожие главы из других книг

Сбор всего вместе

Из книги Время - деньги. Создание команды разработчиков программного обеспечения автора Салливан Эд


ТЕМА НОМЕРА: Вместе — целая страна

Из книги Журнал «Компьютерра» № 19 от 23 мая 2006 года автора Журнал «Компьютерра»

ТЕМА НОМЕРА: Вместе — целая страна Автор: Владимир ГуриевПервая страница сообщества MySpace появилась в онлайне три года назад. Рынок социальных сетей к тому моменту еще не был четко поделен, но сервисов, мягко говоря, хватало. И даже самые большие оптимисты вряд ли могли


Джон Роуз: «Мы собираем людей вместе»

Из книги Журнал «Компьютерра» № 18 от 15 мая 2007 года автора Журнал «Компьютерра»

Джон Роуз: «Мы собираем людей вместе» Автор: Леонид Левкович-МаслюкДоктор Джон Роуз, директор Центра им. Маршалла, отвечал на вопросы «КТ» в парадном кабинете, украшенном многочисленными сувенирами от выпускников, а также изображениями знаменитого соотечественника


Объединяем несовместимое

Из книги Разгони свой сайт автора Мациевский Николай

Объединяем несовместимое С одной стороны, у нас схема data:URI, которая поддержана W3C и распознается всеми браузерами, кроме IE. С другой стороны, у нас IE, который понимает mhtml и с которым работают 70% наших пользователей. Мы объединим эти два решения, благо они оба используют


11.5. Драйверы, поставляемые вместе с компьютером

Из книги Самоучитель работы на компьютере автора Колисниченко Денис Николаевич

11.5. Драйверы, поставляемые вместе с компьютером Обычно с компьютером поставляется как минимум один диск — с драйверами для материнской платы, точнее, для интегрированных в материнскую плату устройств. Если у вас отдельная (а не интегрированная) видеокарта, то будет еще


Собираем все вместе

Из книги Основы объектно-ориентированного программирования автора Мейер Бертран

Собираем все вместе После введения в базовые механизмы ОО-вычислений настало время ответить на вопрос, каким образом можно построить исполняемую систему на основе отдельных


Усадите команду вместе

Из книги Scrum и XP: заметки с передовой автора Книберг Хенрик

Усадите команду вместе Когда приходит время расставить столы и рассадить команду, есть одно правило, которое сложно переоценить.Усадите команду вместе!Чуть поясню, что я имею в виду:Усадите команду вместе!Людям не нравится переезжать. По крайней мере, в тех компаниях, в


1.3.3.4. А теперь — все вместе

Из книги О чём не пишут в книгах по Delphi автора Григорьев А. Б.

1.3.3.4. А теперь — все вместе Комбинация описанных достаточно простых вещей позволяет построить окно с дыркой, имеющей изменяемые размеры.Для начала объявим несколько констант, которые нам потребуются при вычислении размеров дырки и т. п. (листинг 1.51).Листинг 1.51. Константы


45. new и delete всегда должны разрабатываться вместе

Из книги Стандарты программирования на С++. 101 правило и рекомендация автора Александреску Андрей

45. new и delete всегда должны разрабатываться вместе РезюмеКаждая перегрузка void* operator new(parms) в классе должна сопровождаться соответствующей перегрузкой оператора void operator delete(void* , parms), где parms — список типов дополнительных параметров (первый из которых всегда std::size_t). То же


5.3.3. Реклама вместе с Яндексом

Из книги Яндекс для всех автора Абрамзон М. Г.

5.3.3. Реклама вместе с Яндексом Лучше представить свой товар и лучше его продать можно в том случае, когда товар широко рекламируется. Поэтому Яндекс предлагает своим партнерам проведение совместных промоакций. Одним из вариантов таких воздействий на покупателей могут


Глава 7 Соединяя все вместе: ls

Из книги Linux программирование в примерах автора Роббинс Арнольд

Глава 7 Соединяя все вместе: ls Команда V7 ls хорошо связывает воедино все, что мы до сих пор видели. Она использует почти все API, которые мы рассмотрели, затрагивая многие аспекты программирования Unix: выделение памяти, вспомогательные данные файлов, времена и даты, имена


18.5.4. Применение параметров вместе с циклом for

Из книги Linux и UNIX: программирование в shell. Руководство разработчика. автора Тейнсли Дэвид

18.5.4. Применение параметров вместе с циклом for Если в цикле for опустить часть in list, позиционные параметры командной строки становятся аргументами. Действительно, этот подход аналогичен следующему:for params in "$@"илиfor params in "$*"Ниже приводится пример, который показывает, как можно


3.4. Полная анонимность: I2P и Tor вместе

Из книги Анонимность и безопасность в Интернете. От «чайника» к пользователю автора Колисниченко Денис Николаевич

3.4. Полная анонимность: I2P и Tor вместе Наверное, вам интересно, какую сеть использую я? Мой выбор – Tor. Но не потому, что она чем-то лучше I2P, просто больше подходит для моих задач. Сеть I2P удобна, когда нужно обеспечить полную анонимность обмена данными между участниками сети,