re:re:actable
Урок 013 минуты чтения

Что такое алгоритм?

На этой странице
Кратко

Алгоритм - это конечная последовательность шагов, которая получает входные данные, выполняет понятные операции и приводит к нужному результату. На собеседовании важно объяснять не только код, но и идею алгоритма, его корректность и сложность.

Вопрос

Что такое алгоритм и какими свойствами должно обладать корректное решение?

Подсказка

Если вы только начинаете, сначала откройте карту раздела: там порядок изучения и словарь английских терминов (input, output, edge case и других), которые встречаются во всех уроках.

Простое определение

Алгоритм отвечает на вопрос:

Что нужно сделать, в каком порядке и почему это приведет к ответу?

Например, найти максимум в массиве:

function max(nums: number[]): number | null {
  if (nums.length === 0) return null
 
  let answer = nums[0]
 
  for (const num of nums) {
    if (num > answer) answer = num
  }
 
  return answer
}

Идея: храним лучший ответ и обновляем его при встрече большего числа.

Пройдем руками по nums = [3, 8, 2, 9, 4]:

numanswer доnum > answer?answer после
33нет3
83да8
28нет8
98да9
49нет9

Ответ - 9. Такая таблица называется dry run, или трассировка: ее стоит делать для любого нового алгоритма.

Какие свойства есть у хорошего алгоритма?

  • Понятный input - что именно алгоритм получает на вход (nums: number[]).
  • Понятный output - что он возвращает (number | null).
  • Конечное количество шагов - алгоритм обязательно останавливается.
  • Корректность для всех допустимых случаев, а не только для примера из условия.
  • Оценимая сложность - можно сказать, как растет время работы с ростом input (об этом следующий урок).
  • Предсказуемое поведение на edge cases - крайних случаях: пустой массив, один элемент, отрицательные числа. Поэтому в max есть проверка nums.length === 0.

Алгоритм и программа - не одно и то же

Алгоритм - идея решения.

Программа - конкретная реализация.

Один алгоритм binary search можно написать:

  • на JavaScript;
  • на TypeScript;
  • рекурсивно;
  • итеративно;
  • для чисел;
  • для объектов с comparator.

Что отвечать на собеседовании?

Алгоритм - это формальное описание шагов для решения задачи. В интервью я сначала объясняю идею словами, затем показываю инвариант или почему решение корректно, потом пишу код и оцениваю time/space complexity.

Что важно помнить: частые ошибки

  • Начинать писать код без понимания задачи.
  • Не проговаривать edge cases.
  • Считать, что рабочий код автоматически означает хороший алгоритм.
  • Не уметь объяснить, почему решение корректно.
  • Не оценивать сложность.

Мини-шпаргалка

  • Алгоритм - идея и шаги.
  • Код - реализация алгоритма.
  • Важно знать input/output.
  • Важно доказать корректность.
  • Важно оценить сложность.
  • Edge cases проверяются до финального ответа.

Документация

Wikipedia: Algorithm.

Дочитали до конца?
Отметьте урок — прогресс сохранится в браузере.

Поиск

Поиск по урокам