Алгоритмы с нуля
Что такое алгоритм?
Ты следуешь рецепту, чтобы испечь торт. Каждый шаг — смешай муку, добавь яйца, пеки при 350°F в течение 30 минут — это однозначная инструкция. Рецепт работает для каждого, потому что не нужно угадывать. Вот что такое алгоритм в реальной жизни.
После этого урока ты можешь дать точное определение алгоритма, определить вход и выход простого алгоритма и посчитать, сколько шагов нужно, чтобы решить задачу.
Алгоритм — это конечный список однозначных шагов, который превращает вход в выход. Слово «однозначный» — здесь самое важное: каждый шаг должен быть настолько ясным, что компьютер (или человек) мог бы его выполнить без всяких недоразумений. Слово «конечный» означает, что шаги должны когда-нибудь закончиться; алгоритм, который зацикливается навеки, — это не алгоритм.
Посмотри на реальный алгоритм: «Найди наибольшее число в списке». Ты начинаешь со входа — списка чисел. Ты кончаешь с выходом — наибольшим из них. Шаги посредине — это алгоритм.
1
function largestOf(numbers) {
2
let largest = numbers[0];
3
for (let i = 1; i < numbers.length; i++) {
4
if (numbers[i] > largest) {
5
largest = numbers[i];
6
}
7
}
8
return largest;
9
}
- L1 Вход: список чисел
- L5 Ключевой шаг: сравни каждое число с текущим наибольшим
- L8 Выход: вернули найденное наибольшее число
Каждый алгоритм имеет вход (с чего ты начинаешь) и выход (чем ты кончаешь). Шаги посредине превращают вход в выход. Если шаги однозначны и конечны, это алгоритм.
Алгоритм «найди наибольшее число в списке» встречается так часто, что мы напишем его на JavaScript. Вот логика пошагово:
- Предположи, что первое число — наибольшее.
- Посмотри на каждое оставшееся число.
- Если число больше текущего наибольшего, запомни его как новое наибольшее.
- Когда достигнешь конца списка, верни наибольшее.
Вот функция:
function largestOf(numbers) {
let largest = numbers[0];
for (let i = 1; i < numbers.length; i++) {
if (numbers[i] > largest) {
largest = numbers[i];
}
}
return largest;
}Попробуй запустить её со списком [3, 9, 2, 7]. Функция:
- Начнёт с
largest = 3(первое число). - Увидит
9— оно больше, поэтомуlargestстановится9. - Увидит
2— оно меньше9, поэтому пропусти его. - Увидит
7— оно меньше9, поэтому пропусти его. - Вернёт
9.
Смотри, как алгоритм выполняется пошагово на списке [3, 9, 2, 7]:
1
function largestOf(numbers) {
2
let largest = numbers[0];
3
for (let i = 1; i < numbers.length; i++) {
4
if (numbers[i] > largest) {
5
largest = numbers[i];
6
}
7
}
8
return largest;
9
}
Как быстро работает алгоритм? Посчитай шаги: алгоритм посещает каждое из n чисел ровно один раз. Для списка из 4 чисел цикл работает 3 раза (мы пропускаем первое). Для списка из 100 чисел цикл работает 99 раз. Для списка из n чисел цикл работает n − 1 раз.
Мы говорим, что алгоритм работает за O(n) время, что означает число шагов растёт пропорционально размеру входа. Если список удвоится в размере, число шагов примерно удвоится.
Другие алгоритмы поиска наибольшего медленнее. Например, если ты сравнишь каждое число со всеми остальными (проверяя, A > B, B > A и так далее), тебе понадобится n × n сравнений — O(n²) время. Для больших списков это намного хуже.
Ключевая идея: число шагов — это стоимость алгоритма.
Если алгоритм largestOf работает на списке из 10 чисел, сколько сравнений он делает?
Сколько сравнений для списка из 50 чисел?
Какой из этих вариантов — это алгоритм?
Какова временная сложность алгоритма largestOf?
Расставь эти шаги в правильном порядке для алгоритма largestOf:
- Присвой largest первому числу
- Для каждого оставшегося числа проверь, больше ли оно текущего largest
- Если число больше, обнови largest
- Вернули largest
Граничные случаи
Что если список пуст? Алгоритм упадёт при попытке доступа к numbers[0]. Более надёжная версия сначала проверяет, пуст ли список, и обрабатывает это — например, возвращая null или выкидывая ошибку. Реальные алгоритмы должны обрабатывать граничные случаи вроде этого.
Почему важно, чтобы шаги в алгоритме были однозначными?
Алгоритм — это конечный список однозначных шагов, который превращает вход в выход. Каждый алгоритм имеет стоимость, измеряемую числом шагов, которые он требует. Мы используем нотацию большого-O (вроде O(n) или O(n²)), чтобы описать, как число шагов растёт с ростом размера входа. Алгоритм largestOf ищет в списке за O(n) время — посещая каждый элемент один раз.