Алгоритмы и их стоимость

Текстовая версия урока

Как растёт работа с ростом входа — единственный вопрос производительности, который переживает смену железа.

1. Вопрос 1

   В отсортированном списке 1 000 имён. Каждая проверка позволяет отбросить половину оставшегося.

   Сколько проверок понадобится в худшем случае, чтобы найти одно имя?

   Показать ответ и объяснение

   Ответ: 10 проверок

   Объяснение: Деление 1 000 пополам даёт 500, 250, 125, 63, 32, 16, 8, 4, 2, 1 — десять шагов. Бинарный поиск стоит логарифм от размера списка, поэтому поиск среди миллиона записей требует лишь двадцати проверок, а среди миллиарда — тридцати.

   Подсказка: Сколько раз тысячу можно поделить пополам, пока ничего не останется?

2. Вопрос 2

   Вы просматриваете неотсортированный список по одной записи, пока не найдёте нужное.

   Если список станет вдвое длиннее, как изменится работа?

   Варианты

   • ·Останется прежней
   • ·Примерно удвоится
   • ·Примерно учетверится
   • ·Вырастет на один шаг
   Показать ответ и объяснение

   Ответ: Примерно удвоится

   Объяснение: Перебор трогает каждую запись один раз, поэтому удвоение входа удваивает время. Это линейная стоимость, обозначаемая O(n). Вариант D описывает бинарный поиск, которому нужен отсортированный список, — за скорость платят требованием сортировки.

   Подсказка: Вдвое больше записей — вдвое больше того, на что нужно посмотреть.

3. Вопрос 3

   Алгоритм сравнивает каждый элемент с каждым другим.

   Если число элементов удвоится, во сколько примерно раз вырастет работа?

   Варианты

   • ·В два раза
   • ·В четыре раза
   • ·В восемь раз
   • ·Не изменится
   Показать ответ и объяснение

   Ответ: В четыре раза

   Объяснение: Каждый элемент образует пару с каждым, значит количество пропорционально n в квадрате. Удвоение n умножает n² на четыре. Поэтому квадратичный код кажется мгновенным на сотне тестовых строк и полностью встаёт на ста тысячах реальных.

   Подсказка: Длиннее стал и внешний проход, и внутренний.

4. Вопрос 4

   Кто-то загадал целое число от 1 до 100. После каждой догадки вам говорят, больше загаданное число или меньше.

   Сколько догадок понадобится в худшем случае при оптимальной стратегии?

   Показать ответ и объяснение

   Ответ: 7 догадок

   Объяснение: Называя середину, вы каждый раз делите диапазон пополам: 100, 50, 25, 13, 7, 4, 2, 1. Семи догадок всегда хватает, потому что 2 в седьмой степени равно 128 и покрывает 100. Шесть покрыли бы лишь 64 варианта, поэтому гарантии не дают.

   Подсказка: Всегда называйте середину и посчитайте, сколько делений пополам выдержит 100.

5. Вопрос 5

   Квадратичный алгоритм обрабатывает 1 000 записей за 1 секунду.

   Сколько примерно секунд займут 10 000 записей?

   Показать ответ и объяснение

   Ответ: 100 секунд

   Объяснение: Десятикратный вход означает стократную работу для квадратичного алгоритма, поэтому одна секунда превращается примерно в сто. Заметьте, что вдвое более быстрая машина отыгрывает лишь двойку — темп роста всегда побеждает железо, поэтому форма алгоритма важнее сервера, на котором он работает.

   Подсказка: Вход вырос в десять раз, а стоимость идёт по квадрату.