Недавно решал задачку на литкоде и сначала радовался, как я ловко с ней справился, а потом обнаружил, что моё решение далеко от самого эффективного. Проблема была в том, что я даже не подумал использовать один алгоритм, который мы ещё в универе проходили (и который, наверно, могут спросить на каком-нибудь собесе). И я решил повторить и законспектировать все важные моменты по этой теме. Начну с основных понятий и простейших алгоритмов (сортировка, поиск элемента в списке).
Алгоритм – это набор инструкций, которые описывают, как получить необходимый результат. Примеры алгоритмов на естественном языке это рецепты блюд, инструкции по сборке мебели или настройке бытовой техники, или подсказки по прохождению игры.
Нас в универе (и наверно ещё на уроках информатики в школе) учили, что основные свойства алгоритмов:
- Понятность. Написан на понятном для исполнителя языке.
- Дискретность. Разбит на отдельные шаги (команды).
- Детерменированность. В любой момент чётко определён следующий шаг. Таким образом, алгоритм должен давать одни и те же результаты для одних и тех же входных данных.
- Результативность. Выполнение алгоритма всегда приводит к результату, и не оставляет неопределённости.
- Конечность. Должен завершаться и выдавать результат за определённое число шагов.
- Массовость. Каждый алгоритм можно использовать для похожих задач с разными входными данными.
Такое определение алгоритма легко и понятно, но не всегда верно. Также бывают варианты стохастические (которые содержат случайные величины) или приблизительные (которые не находят точное значение).
Алгоритмы могут быть линейными, могут содержать ветвления и циклы, но особенно важна рекурсия, которую лично я не особо люблю использовать, а зря.
Каждому алгоритму можно сопоставить вычисляемую функцию, а функции могут быть рекурсивными. Такие функции вызывают сами себя для решения задачи уже меньшего размера. Важное условие – наличие базового случая, то есть момента, в котором дальнейшие вызовы этой же функции завершаются.
Примеры рекурсивных функций
Рассмотрим примеры рекурсивных функций для вычисления степени и факториала.
public int factorial(int n) {
if (n == 0) {
return 1;
}
return n * (factorial(n-1));
} public int power(int n, int pow) {
if (pow == 0) {
return 1;
}
return n * power(n, pow-1);
}В первой функции базовым случаем является факториал нуля – он равен единице. Если число больше нуля, то мы продолжаем умножение с рекурсивным вызовом.
Во второй функции базовым случаем является нулевая степень – также единица. Иначе мы продолжаем умножать число на себя, но уже на один раз меньше.
Теперь попробуем найти максимальный элемент в списке с помощью рекурсивной функции.
public int findMax(List<Integer> numbers, int index) {
if (index == numbers.size() - 1) {
return numbers.get(index);
}
int maxInRest = findMax(numbers, index + 1);
return numbers.get(index) > maxInRest ? numbers.get(index) : maxInRest;
}
public static void main(String[] args) {
List<Integer> nums = List.of(3, 7, 2, 9, 5, 10, 6);
int max = findMax(nums, 0);
System.out.println("Максимум: " + max);
}Здесь мы рекурсивно уменьшаем область поиска максимума в списке пока не достигаем базового случая – списка из одного последнего элемента. В этой области очевидно, что максимум этот самый единственный элемент. После этого мы «раскручиваем» наш стэк вызовов и сравниваем максимум с предыдущим элементом, потом максимум из этих двух чисел – с ещё предыдущим, максимум из трёх чисел – с предыдущим, и так далее, пока не придём к началу.
Сложность алгоритмов и Big-O нотация
Алгоритмы создаются для работы с данными, поэтому важно уметь оценивать их эффективность. Это помогает выбрать подходящий алгоритм из нескольких вариантов.
Главный вопрос, на который необходимо ответить: как меняется время работы в зависимости от объёма входных данных?
Для этого используют специальный способ записи – Big-O нотацию. Она описывает, как растёт время выполнения алгоритма при увеличении объёма данных. Буква O в обозначении идёт от слова order (порядок роста). Часто она оценивает худший случай – сколько максимально времени может занять операция.
Основные классы сложности
Ниже перечислю основные классы сложности от лучшего к худшему:
- O(1) – константное время
Время работы не зависит от количества данных.
Примеры: доступ к элементу массива по индексу (хоть один элемент в массиве, хоть их сто – эта операция занимает одно и то же время). - O(log n) – логарифмическое время
Работает эффективно при увеличении объёмов данных.
Пример: бинарный поиск в отсортированном массиве. Даже при большом массиве количество шагов растёт медленно (см. реализацию алгоритма ниже)
Log n здесь, потому что в этом алгоритме мы на каждом шаге делим массив на две части, пока не найдём нужный элемент. То есть число операций – это то число, в которое нужно возвести двойку, чтобы получить длину массива. Если элементов всего 2 – у нас будет одна операция, если их 4 – уже 2, если 18, то 5 , а если 1000, то всего 10.
- O(n) – линейное время
Время выполнения прямо пропорционально количеству элементов.
Пример: поиск элемента в неотсортированном массиве. Чем больше элементов, тем дольше искать, так как нам в худшем случае нужно пройтись по всем элементам. - O(n log n) – линейно-логарифмическое время
Характерно для многих эффективных алгоритмов сортировки.
Примеры: сортировка слиянием, сортировка кучей (см алгоритмы сортировки в следующей статье). - O(n²) – квадратичное время
Очень неэффективно на больших данных: при увеличении массива в два раза время растёт в четыре раза.
Примеры: сортировка пузырьком, сортировка выбором (простые алгоритмы сортировки).
Примеры алгоритмов и определение их сложности по Big-O нотации
Константное время для доступа к первому элементу массива:
int getFirstElement(int[] arr) {
return arr[0];
}Линейное время для суммы всех чисел в массиве. Цикл намекает на то, что сложность будет O(n).
int sum(int[] arr) {
int total = 0;
for (int value : arr) {
total += value;
}
return total;Квадратичное время для вывода всевозможных пар чисел из массива. Тут у нас два вложенных цикла, поэтому (для каждого по n, как в прошлом примере). В итоге n*n = O(n²)
void printPairs(int[] arr) {
for (int i = 0; i < arr.length; i++) {
for (int j = 0; j < arr.length; j++) {
System.out.println(arr[i] + ", " + arr[j]);
}
}
}Алгоритм поиска элемента в неотсортированном массиве
Я выше обещал описать пару алгоритмов поиска. Начнём с неотсортированного массива. Мы не знаем, на каком месте находится искомый элемент, поэтому просто перебираем все элементы по очереди, пока не найдём нужный.
public static int findItem(int[] a, int number) {
for (int i = 0; i < a.length; i++) {
if (a[i] == number)
return i;
}
return -1;
}Так как тут у нас есть цикл, который в худшем случае (если нужный элемент в конце или вообще не встречается) должен перебрать все элементы, то получаем O(n).
Алгоритм бинарного поиска в отсортированном массиве
Так как массив отсортирован, мы можем каждый раз сокращать область поиска в два раза. Если элемент находится посередине области, то возвращаем его. Иначе смотрим, меньше он или больше середины. Если меньше, то ищем так же слева. Если больше, то ищем так же справа. Если не нашли его, то возвращаем -1.
Из-за таких сокращений области поиска в два раза получаем O(log n)
public static int binarySearch(int[] a, int target) {
int left = 0;
int right = a.length - 1;
while (left <= right) {
int mid = (left + right) / 2;
if (a[mid] == target) {
return mid;
} else if (a[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1;
}Тут так же напрашивается рекурсивный вариант вместо цикла. Логика та же.
public static int binarySearchRecursive(int[] a, int target, int left, int right) {
if (left > right) {
return -1;
}
int mid = (left + right) / 2;
if (a[mid] == target) {
return mid;
} else if (a[mid] < target) {
return binarySearchRecursive(a, target, mid + 1, right);
} else {
return binarySearchRecursive(a, target, left, mid - 1);
}
}Вызов такого варианты будет с начальными границами (первый и последний элемент):
int index = binarySearchRecursive(a, target, 0, a.length - 1);Алгоритм поиска всех перестановок массива
Теперь оценим сложность моего решения задачи с leetcode по поиску всех перестановок (создаются списки с теми же элементами, но во всех возможных последовательностях):
class Solution {
void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
void permute(int[] arr, int index, List<List<Integer>> list) {
if (index == arr.length) {
List<Integer> list1 = Arrays.stream(arr)
.boxed()
.collect(Collectors.toList());
list.add(list1);
return;
}
for (int i = index; i < arr.length; i++) {
swap(arr, index, i);
permute(arr, index + 1, list);
swap(arr, index, i);
}
}
public List<List<Integer>> permute(int[] nums) {
List<List<Integer>> list = new ArrayList<>();
permute(nums, 0, list);
return list;
}
}Здесь в основном методе permute у нас есть цикл, который уже даёт нам n прохождений. В каждом прохождении мы вызываем ту же функцию рекурсивно. В каждом вызове функция делает до n проходов, затем n-1, n-2 и так далее. Это даёт n! перестановок. Плюс каждый результат нужно скопировать в список (O(n)). Итого сложность O(n · n!).
Поиск самого длинного палиндрома в строке
И рассмотрим ещё одну задачу с литкода – поиск самого длинного палиндрома в строке.
class Solution {
private boolean isPalindrome(String s) {
for (int i = 0; i < s.length()/2; i++) {
if (s.charAt(i) != s.charAt(s.length() - i - 1))
return false;
}
return true;
}
public String longestPalindrome(String s) {
final int length = s.length();
int n = 1;
int shortenIndex = 0;
int lengthSub = length;
while (true) {
for (int i = 0; i < n; i++) {
if (isPalindrome(s.substring(i, i + lengthSub))) {
return s.substring(i, i + lengthSub);
}
}
shortenIndex++;
n++;
lengthSub = length - shortenIndex;
}
}
}В своём решении я сначала проверяю всю строку, потом проверяю две подстроки длиной length – 1, потом три строки длиной length – 2, и так далее, пока не найду первый встретившийся палиндром – он и будет гарантировано одним из самых длинных.
В этом случае два вложенных цикла, которые в худшем случае уже дают O(n²). И также есть дополнительная проверка, является ли подстрока палиндромом – ещё n. Итого O(n3).
Для сравнения рассмотрим самое эффективное решение, которое предложили другие пользователи.
class Solution {
public String longestPalindrome(String s) {
int n=s.length();
int maxLen=Integer.MIN_VALUE;
int start=-1;
for(int i=0;i<n;i++){
for(int j=0;j<=1;j++){
int l=i;
int h=i+j;
while(l>=0 && h<n && s.charAt(l)==s.charAt(h)){
int currLen=h-l+1;
if(maxLen<currLen){
maxLen=currLen;
start=l;
}
l--;
h++;
}
}
}
return s.substring(start,start+maxLen);
}
}Здесь внешний цикл даёт нам n, но внутренний цикл for выполняет каждый раз всего два прохождения: то есть получаем 2n – O(n).
А вот цикл while даёт ещё одно прохождение – получаем O(n²).
Интересно, что «эффективный» алгоритм всегда работает за O(n²), даже на строке, которая уже является палиндромом. А моё решение в таком случае сработает быстрее – за O(n). Но в худшем случае оно проваливается до O(n³), поэтому в среднем и больших задачах второй вариант выигрывает.
На этом сегодня остановлюсь. Дальше я хочу разобрать основные алгоритмы сортировки – от пузырька до быстрой сортировки.
Zimowski Journal 