Что такое алгоритмы в программировании

Алгоритмы — тема, с которой вы с высокой вероятностью столкнетесь на собеседовании. Они используются в математике, физике, биологии, информатике. Но особенно они важны для программистов.

Что такое алгоритмы и зачем они нужны?

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

Алгоритмы нужны для:

1. Получения результата более эффективным и быстрым путем
2. Уменьшения количества ошибок, которые возникают при решении задач вручную
3. Переиспользования, чтобы не «изобретать велосипед».

Алгоритмы окружают нас повсюду, в том числе и в быту:

1. Рецепт борща
2. Инструкция по сборке мебели
3. Набор действий для оплаты товаров на маркетплейсах
4. План обучения в колледже
5. Создание учетной записи.

В программировании алгоритмы используются для автоматизации процессов и упрощения решения задач, например в:

1. Сортировке и поиске данных в массивах и базах данных
2. Тестировании выпускаемого программного продукта
3. Разработке игр и приложений, чтобы определять поведение персонажей и реагировать на действия пользователя
4. Криптографии для защиты данных в системах безопасности и шифровании информации при передаче по сети
5. Системах рекомендаций для пользователей
6. Научных и медицинских исследованиях
7. Разработке искусственного интеллекта и в машинном обучении, чтобы обучать компьютеры распознавать образы и голосовые команды.

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

1. Дискретность: алгоритм должен состоять из конечного набора последовательных шагов. Каждое новое действие начинается после того, как исполнилось предыдущее. Например:

function sumNumbers(numbers) {
  let sum = 0;
  for (let i = 0; i < numbers.length; i++) {
    sum += numbers[i];
  }
  return sum;
}

Этот алгоритм принимает входной массив чисел и возвращает их сумму. Он состоит из последовательных шагов, таких как присвоение переменной sum значение равное 0, использование цикла for для прохода по элементам массива, и увеличение значения переменной sum на каждой итерации цикла.

Данный алгоритм демонстрирует дискретные свойства, потому что он может быть описан конечным набором дискретных шагов, и каждый шаг выполняется явно и последовательно. Это позволяет программистам легко понимать и анализировать алгоритмы и обеспечивает их эффективность и надежность.

2. Результативность: алгоритм всегда завершается и возвращает правильный результат.

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

Алгоритм принимает входной массив чисел и возвращает максимальное число в массиве. Он начинается с инициализации переменной max первым элементом массива numbers. Затем он проходит циклом for по оставшимся элементам массива и сравнивает каждый элемент с текущим максимальным значением max. Если текущий элемент больше, то он становится новым максимальным значением.

После прохождения цикла алгоритм возвращает максимальное значение max. Таким образом, этот алгоритм всегда завершается и возвращает правильный результат, что демонстрирует его свойство результативности.

3. Детерминированность: для одного и того же входного значения алгоритм всегда должен давать одинаковый результат, примером может служить конечный автомат:

function isPalindrome(str) {
  const transitions = {
    0: { '': 0, 'a': 1, 'b': 2 },
    1: { '': 3, 'a': 1, 'b': 4 },
    2: { '': 3, 'a': 4, 'b': 2 },
    3: { '': 5 },
    4: { '': 5 },
    5: {}
  };
  let state = 0;
  for (let i = 0; i < str.length; i++) {
    const input = str[i];
    if (!transitions[state][input]) {
      return false;
    }
    state = transitions[state][input];
  }
  return state === 3 || state === 4;
}

console.log(isPalindrome('ababa')); // true
console.log(isPalindrome('abab')); // false

Код выше  — реализация конечного автомата. Он проверяет, является ли заданная строка палиндромом (строка читается одинаково справа налево и слева направо).

Конечный автомат — это модель, которая может находиться в одном из конечного числа состояний, и изменять свое состояние в зависимости от входных данных. Если вы запустите конечный автомат с одним и тем же начальным состоянием и входными данными, то результат всегда будет одинаковым.

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

function sumArray(arr) {
  let sum = 0;
  for (let i = 0; i < arr.length; i++) {
    sum += arr[i];
  }
  return sum;
}

const array1 = [1, 2, 3, 4, 5];
const array2 = Array.from({length: 1000000}, () => Math.floor(Math.random() * 100));

console.time('sumArray1');
console.log(sumArray(array1));
console.timeEnd('sumArray1');

console.time('sumArray2');
console.log(sumArray(array2));
console.timeEnd('sumArray2');

Алгоритм принимает массив чисел и возвращает их сумму. Он использует цикл for, чтобы перебрать все элементы массива и добавить их к переменной sum. Функция console.time используется для измерения времени выполнения алгоритма.

Для сравнения имеются два массива: array1, который содержит всего 5 элементов, и array2, который содержит 1 миллион элементов. Однако, благодаря использованию цикла for, время выполнения алгоритма остается примерно одинаковым в обоих случаях.

5. Понятность: алгоритм должен быть понятен для исполнителя и других программистов, которые могут его использовать. Вспомним пример, который уже приводился выше:

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

А теперь сравним с другим примером:

function hrleh(oooo) {
  let m = oooo[0];
  for (let g = 1; g < oooo.length; g++) {
    if (oooo[g] > m) {
      m = oooo[g];
    }
  }
  return m;
}

Алгоритм первого кода прост в понимании даже для людей, которые не имеют большого опыта программирования. Он использует основные конструкции языка JavaScript и не содержит сложных операций или абстракций. Кроме того, он хорошо структурирован и имеет понятное название функции, которое описывает ее цель. Все это делает этот алгоритм понятным и легко читаемым.

6. Конечность: алгоритм должен иметь определенное количество шагов, которые он выполняет, и в конце концов завершаться.

Приведенный выше алгоритм складывает все числа в массиве numbers. Он имеет конечное количество шагов: он просто проходит по каждому элементу массива и складывает его с общей суммой. Как только он проходит все элементы массивы, он возвращает общую сумму.

Конечность алгоритмы закоючается в том, что он всегда останавливается после того, как пройдет все элементы массива.

Виды алгоритмов

1. Линейные: действия выполняются по порядку, друг за другом. Например:

function sum(numbers) {
  let total = 0;
  for (let i = 0; i < numbers.length; i++) {
    total += numbers[i];
  }
  return total;
}

Алгоритм начинается с первого элемента массива и последовательно выводит каждый элемент в консоль. Он выполняет действия по порядку без пропусков или повторений. Как только последний элемент массива будет выведен, алгоритм завершится.

2. Ветвящиеся: выполнение различных операций в зависимости от входящих условий. Например:

if (number > 0) {
  console.log("Число больше нуля");
} else if (number === 0) {
  console.log("Число равно нулю");
} else {
  console.log("Число меньше нуля");
}

Этот алгоритм проверяет значение переменной number и выводит различный текст в зависимости от того, какое значение имеет переменная. Если number больше нуля, то выводится сообщение "Число больше нуля". Если number равно нулю, то выводится сообщение "Число равно нулю". Если number меньше нуля, то выводится сообщение "Число меньше нуля". Это пример ветвящегося алгоритма, потому что он делает различные ветвления в зависимости от значения переменной number.

3. Циклические: повторение операций несколько раз. Изучим цикл, который повторяется, пока переменная i меньше пяти:

let i = 0;

while (i < 5) {
  console.log(i);
  i++;
}

Каждый раз, когда цикл выполняется, он выводит значение переменной i на консоль и увеличивает ее на единицу. Как только переменная i достигает значения 5, цикл завершается. Это пример циклического алгоритма, потому что он выполняет повторяющиеся действия в цикле, пока не будет выполнено определенное условие.

4. Рекурсивные: вызов алгоритма из самого себя. Рассмотрим рекурсию для вычисления факториала числа n:

function factorial(n) {
  if (n === 1) {
    return 1;
  } else {
    return n * factorial(n - 1);
  }
}

console.log(factorial(5)); // 120

Если n равно 1, то функция возвращает 1. В противном случае функция вызывает саму себя с аргументом n - 1 и умножает результат на n. Как только n достигает значения 1, рекурсия заканчивается, и функция начинает возвращать значения из рекурсивных вызовов. Это пример рекурсивного алгоритма, потому что он использует вызов функции из самой себя.

5. Вероятностные: использование случайных чисел для решения задач, например с помощью Math.random():

function randomBoolean() {
 return Math.random() < 0.5;
}

В этом примере функция randomBoolean() генерирует случайное число с помощью метода Math.random(), который возвращает псевдослучайное число между 0 и 1. Затем функция сравнивает это число с 0,5 и возвращает true, если оно меньше 0,5, и false, если оно больше или равно 0,5. Таким образом, функция будет возвращать true и false с равной вероятностью.

Сортировки

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

От чего зависит сложность алгоритма?

Сложность алгоритма — это количество операций, которые необходимо выполнить для решения задачи. Она зависит от:

1. Размера входных данных: сложность алгоритма возрастает с увеличением размера входных данных
2. Времени выполнения: хорошо написанные алгоритмы работают быстрее, чем другие, что влияет на время выполнения
3. Ограничений ресурсов: размер доступной памяти, мощность процессора или место на сервере влияют на результат
4. Наличия вложенных циклов или рекурсивных вызовов: вложенные циклы или рекурсивные вызовы увеличивают количество операций, необходимых для выполнения алгоритма.

Сложность алгоритма измеряется в большой О-нотации (Big-O notation), которая показывает, как быстро растет время выполнения алгоритма при увеличении размера входных данных.