Введение и проблематика

В программировании мы постоянно решаем задачи: отсортировать список, найти элемент, обработать данные. Но как объяснить компьютеру, что именно нужно сделать? Для этого существуют алгоритмы.

Какую проблему решает понятие алгоритма?

Алгоритм позволяет:

• Формализовать решение задачи в виде пошаговой инструкции
• Передать это решение исполнителю (человеку или компьютеру)
• Гарантировать получение результата при корректных входных данных

Базовая теория

Определение

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

Свойства алгоритма

Любой алгоритм должен обладать пятью ключевыми свойствами:

Алгоритм vs Программа

• Алгоритм — абстрактное описание решения, независимое от языка
• Программа — реализация алгоритма на конкретном языке программирования

Способы записи алгоритмов

Алгоритм можно представить разными способами:

Алгоритм поиска максимума в массиве:
1. Взять первый элемент как текущий максимум
2. Для каждого следующего элемента:
   - Если элемент больше текущего максимума,
     обновить максимум
3. Вернуть максимум

Практические примеры

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

function isEven(n) {
  return n % 2 === 0;
}
 
// Примеры использования
console.log(isEven(4));  // true
console.log(isEven(7));  // false

Пример 2: Алгоритм линейного поиска

function linearSearch(arr, target) {
  // Проходим по каждому элементу массива
  for (let i = 0; i < arr.length; i++) {
    // Если нашли искомый элемент — возвращаем индекс
    if (arr[i] === target) {
      return i;
    }
  }
  // Элемент не найден
  return -1;
}
 
const numbers = [5, 2, 8, 1, 9];
console.log(linearSearch(numbers, 8)); // 2
console.log(linearSearch(numbers, 3)); // -1

Классификация алгоритмов

По структуре

По назначению

• Сортировка: bubble sort, quick sort, merge sort
• Поиск: линейный, бинарный
• Обход графов: BFS, DFS
• Строковые: поиск подстроки, сравнение

Пограничные кейсы

Типичные граничные случаи:

• Пустой массив — что вернёт алгоритм поиска максимума?
• Один элемент — корректно ли обрабатывается?
• Отрицательные числа — учтены ли в логике?
• Дубликаты — как алгоритм работает с повторяющимися значениями?

function findMax(arr) {
  // Обработка граничного случая
  if (arr.length === 0) {
    return undefined; // или throw new Error('Массив пуст')
  }
 
  let max = arr[0];
  for (let i = 1; i < arr.length; i++) {
    if (arr[i] > max) {
      max = arr[i];
    }
  }
  return max;
}

Плюсы и минусы

Преимущества алгоритмического мышления

• Структурированность — задача разбивается на понятные шаги
• Повторяемость — одинаковый вход даёт одинаковый выход
• Анализируемость — можно оценить сложность и эффективность
• Универсальность — алгоритм не привязан к языку программирования

Ограничения

• Не всё алгоритмизируемо — существуют неразрешимые задачи
• Компромиссы — часто приходится выбирать между временем и памятью
• Сложность разработки — оптимальный алгоритм не всегда очевиден

Вопросы интервьюера

Q: Чем алгоритм отличается от программы?

Алгоритм — это абстрактное описание последовательности действий, независимое от языка программирования. Программа — конкретная реализация алгоритма на определённом языке.

Q: Какие свойства должен иметь алгоритм?

Конечность, определённость, наличие входа и выхода, эффективность.

Q: Приведите пример задачи, которую нельзя решить алгоритмически?

Проблема останова (halting problem) — невозможно создать алгоритм, который определит, остановится ли произвольная программа.

Q: Что такое сложность алгоритма?

Это мера ресурсов (времени или памяти), необходимых для выполнения алгоритма в зависимости от размера входных данных. Обычно выражается через O-нотацию.

Источники

• MDN: Algorithms
• Khan Academy: Algorithms
• Кормен Т. и др. «Алгоритмы: построение и анализ»