Алгоритмы с нуля

Подсчёт шагов

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

◷ 18 min

Предположим, ты написал два алгоритма для решения одной задачи. Один посещает каждый элемент списка один раз. Другой посещает каждую пару элементов. Для списка из 100 элементов первый делает 100 шагов, второй — 10 000. Откуда мы это узнали? Мы подсчитали шаги. Вот так ты измеряешь цену алгоритма ещё до его запуска.

Цель

После этого урока ты можешь подсчитать число базовых шагов, которые выполняет алгоритм, как функцию от размера входа n, предсказать, как это число растёт (линейно, квадратично и так далее), и понять, почему скорость роста важнее точного числа.

Идея

Базовая операция — это шаг, который компьютер выполняет за постоянное время: присваивание, сравнение, арифметика, доступ к элементу массива. Каждый алгоритм построен из многих базовых операций. Число шагов алгоритма — это сколько базовых операций он выполняет на данном входе.

Ключевой вывод: число шагов зависит от размера входа. Для функции largestOf (из урока 01) вход — это список из n чисел. Число шагов примерно n − 1 (одно сравнение на элемент после первого). Для другого алгоритма, проверяющего каждую пару элементов, число шагов примерно n × n.

Подсчитаем шаги для largestOf:


      1
      function largestOf(numbers) {
    

      2
      let largest = numbers[0];           // 1 шаг
    

      3
      for (let i = 1; i < numbers.length; i++) {
    

      4
        if (numbers[i] > largest) {       // 1 сравнение за итерацию
    

      5
          largest = numbers[i];           // 1 присваивание (иногда)
    

      6
        }
    

      7
      }
    

      8
      return largest;                     // 1 шаг
    

      9
      }

L1 Инициализация: 1 присваивание
L2 Цикл выполняется n-1 раз. Каждая итерация делает 1 сравнение + возможно 1 присваивание
L6 Возврат: 1 шаг

Внутри цикла критическая операция — это сравнение numbers[i] > largest. Это происходит ровно n − 1 раз (один раз для каждого элемента после первого). Значит, число шагов — примерно n − 1.

Теперь рассмотрим другой алгоритм: подсчитай, сколько пар одинаковых чисел в списке. Чтобы проверить каждую пару, нужны вложенные циклы:

function countEqualPairs(numbers) {
  let count = 0;
  for (let i = 0; i < numbers.length; i++) {
    for (let j = i + 1; j < numbers.length; j++) {
      if (numbers[i] === numbers[j]) {
        count++;
      }
    }
  }
  return count;
}

Внешний цикл выполняется n раз. Внутренний цикл выполняется примерно n раз (в среднем). Итого примерно n × n = n² сравнений. Для списка из 100 элементов это 10 000 сравнений. Для списка из 1 000 элементов это 1 000 000 сравнений.

Число шагов — это функция от n. Пишем:

largestOf имеет число шагов примерно n − 1.
countEqualPairs имеет число шагов примерно n².

Важно, как число шагов растёт в зависимости от n, не точное число. Если удвоить n, число шагов для largestOf примерно удвоится. Если удвоить n для countEqualPairs, число шагов примерно учетверится (потому что n² растёт намного быстрее, чем n).

Код

Реализуем оба алгоритма и подсчитаем шаги вручную.

Алгоритм 1: найди наибольшее число

function largestOf(numbers) {
  let largest = numbers[0];
  for (let i = 1; i < numbers.length; i++) {
    if (numbers[i] > largest) {
      largest = numbers[i];
    }
  }
  return largest;
}

Алгоритм 2: подсчитай пары одинаковых чисел

function countEqualPairs(numbers) {
  let count = 0;
  for (let i = 0; i < numbers.length; i++) {
    for (let j = i + 1; j < numbers.length; j++) {
      if (numbers[i] === numbers[j]) {
        count++;
      }
    }
  }
  return count;
}

Попробуй оба на маленьком списке:

Вывод

Оба работают, но заметь: largestOf быстр даже на больших списках. countEqualPairs растёт намного медленнее при увеличении размера списка.

Пошаговый разбор

Трассируем countEqualPairs на маленьком списке [3, 9, 3] и подсчитаем сравнения:


      1
      function countEqualPairs(numbers) {
    

      2
        let count = 0;
    

      3
        for (let i = 0; i < numbers.length; i++) {
    

      4
          for (let j = i + 1; j < numbers.length; j++) {
    

      5
            if (numbers[i] === numbers[j]) {
    

      6
              count++;
    

      7
            }
    

      8
          }
    

      9
        }
    

      10
        return count;
    

      11
      }

Для n = 3 мы сделали 3 сравнения. Для n = 4 было бы 6 сравнений (1 + 2 + 3). Для n = 5 было бы 10 сравнений (1 + 2 + 3 + 4). Паттерн — n × (n − 1) / 2, что примерно n².

Сложность

Теперь подумаем о росте. Предположим, мы знаем число шагов как функцию от n:

largestOf: число шагов ≈ n − 1
countEqualPairs: число шагов ≈ n × (n − 1) / 2, что примерно n²

Что происходит, когда n удваивается?

Размер входа n	шаги largestOf	шаги countEqualPairs
10	9	45
20	19	190
100	99	4 950
200	199	19 900

Заметь: когда n идёт от 10 к 100, шаги largestOf идут от 9 к 99 (10× увеличение). Но шаги countEqualPairs идут от 45 к 4 950 (110× увеличение). Квадратичный рост намного хуже линейного.

Почему это важно? Когда вход становится больше, алгоритм с квадратичным числом шагов становится непрактичным намного быстрее, чем один с линейным числом шагов. Для обработки миллиона элементов линейный требует 1 миллион шагов; квадратичный требует 1 триллион шагов.

Доминирующий член — вот что имеет значение. Для countEqualPairs, членterm n² доминирует; линейный и постоянные члены пренебрежимо малы. Для largestOf, член n доминирует.

Нам важно, как число шагов растёт в зависимости от n, не точное число.

Практика 0 / 5

Сколько сравнений делает largestOf на списке из 50 элементов?

Для countEqualPairs на списке из 4 элементов, сколько сравнений? (Подсказка: 1 + 2 + 3.)

Если n идёт от 10 к 100, примерно во сколько раз увеличиваются шаги для алгоритма с числом шагов ~n?

Если n идёт от 10 к 100, примерно во сколько раз увеличиваются шаги для алгоритма с числом шагов ~n²?

Расставь эти числа шагов в порядке роста (медленнее вперёд):

Число шагов = n²
Число шагов = n
Число шагов = 1 (постоянное)
Число шагов = n × (n − 1) / 2

Граничные случаи

Подсчёт констант. На практике константы имеют значение для фактического времени выполнения (один алгоритм может делать 2n шагов, другой 5n), но для понимания роста константа не меняет общую картину. Алгоритм, который делает 100n шагов, и тот, что делает n шагов, оба растут линейно — они масштабируются одинаково. Следующий урок вводит Big-O нотацию, которая игнорирует константы и сосредоточена на росте.

Частая ошибка

Забывчивость о вложенных циклах. Частая ошибка: видишь один цикл и думаешь, что число шагов линейное. Но вложенные циклы всё меняют. Цикл внутри цикла — не 2n; это n × n. Цикл внутри цикла внутри цикла — это n³. Всегда подсчитывай вложение.

Проверь себя

Викторина

Алгоритм имеет число шагов примерно 3n + 5. Если n удвоится, примерно во сколько раз увеличится число шагов?

Итог

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

Один цикл через n элементов: число шагов ≈ n
Вложенные циклы по всем парам: число шагов ≈ n²

При росте n число шагов растёт. Линейные алгоритмы (число шагов ~n) растут с постоянной скоростью; квадратичные алгоритмы (число шагов ~n²) растут намного быстрее. Важен доминирующий член и скорость роста, не точное число шагов или константы. Следующий урок формализует эту идею с помощью Big-O нотации.

Продолжить восхождение ↑Нотация Big-O