TwiddleLab / Код / Алгоритмы в движении

Считаем шаги

Урок 1 из 11 · 5 мин · Бесплатно, без аккаунта

Что ты узнаешь

• Число шагов это сколько базовых шагов делает программа. Оно растёт вместе с размером данных n.
• Один цикл по n элементам занимает около n шагов: удвой n, удвоятся шаги.
• Цикл внутри цикла занимает около n x n шагов: удвой n, шагов станет в четыре раза больше.
• Поэтому время работы на миллионе элементов можно предсказать по одному коду.

Начать урок

Как идёт урок

1. Твой код работает на 10 песнях. На миллионе он зависает. Можно было это предсказать?

   Две программы, те же 10 песен. Запусти их и смотри на счётчики.

2. Теперь 20 песен вместо 10. Где остановится счётчик пар?

   Для 10 песен он показал 100. Догадка подойдёт.

3. Удваивай песни снова и снова.

   Смотри на ряд и на квадрат. Дойди до 160.

   Программа пар запускает внутренний цикл n раз для каждого из n значений i. Это n x n. Для 2n песен это 2n x 2n = 4 x n x n.

4. Считаем шаги.

   Число шагов это сколько базовых шагов делает программа, например сравнений двух песен. Размер данных мы обозначаем n.

   Один цикл по n элементам: около n шагов. Удвой n, и шаги удвоятся.

   Цикл внутри цикла: около n x n шагов. Удвой n, и шагов станет в 4 раза больше. Этот рост это время работы программы под маской.

5. Предскажи счётчик.

   Каждая программа добавляет 1 к steps. Угадай итоговое число, потом «Запуск». Собери серию.

6. Сколько песен в твоей библиотеке?

   Примерно подойдёт. Посмотри, сколько займёт каждая программа.

7. Твоя библиотека выросла в 10 раз. Какая программа зависнет?

   Нажми на программу, потом «Проверить».

   Просмотр растёт как n, поэтому 10n песен займут в 10 раз больше времени. Пары растут как n x n, поэтому 10n песен займут в 10 x 10 = 100 раз больше.

Следующий урок: Линейный и двоичный поиск, снова · Часть курса: Алгоритмы в движении

Уроки интерактивные и работают на JavaScript. Включи его, чтобы играть.