Что такое алгоритм?
На этой странице
Алгоритм - это конечная последовательность шагов, которая получает входные данные, выполняет понятные операции и приводит к нужному результату. На собеседовании важно объяснять не только код, но и идею алгоритма, его корректность и сложность.
Вопрос
Что такое алгоритм и какими свойствами должно обладать корректное решение?
Если вы только начинаете, сначала откройте карту раздела: там порядок изучения и словарь английских терминов (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]:
| num | answer до | num > answer? | answer после |
|---|---|---|---|
| 3 | 3 | нет | 3 |
| 8 | 3 | да | 8 |
| 2 | 8 | нет | 8 |
| 9 | 8 | да | 9 |
| 4 | 9 | нет | 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 проверяются до финального ответа.