Что такое алгоритм? Мне нравится думать, что алгоритм – это набор правил, определяющих, как решить проблему. Алгоритм может быть определен за пределами информатики, в математике, природе или дорожном движении. В информатике алгоритм является абстрактным и не имеет машинной реализации.
Наиболее важным “инструментом” для манипулирования при кодировании являются структуры данных , и именно это является отправной точкой на пути к алгоритмам. Структуры данных – это просто способ организации данных. Однако, если быть более конкретным, кто бы сказал лучше, чем Википедия, верно?
Структура данных – это набор значений данных, связей между ними и функций или операций, которые могут быть применены к данным.
Сейчас самое подходящее время заняться темой анализа сложности . Это процесс определения того, насколько эффективен алгоритм. Поэтому мы сосредоточимся на двух измерениях – временной и пространственной сложности.
Временная сложность – это показатель скорости выполнения алгоритма, и она выражается с помощью обозначения Big O .
Сложность пространства – это показатель того, сколько вспомогательной памяти занимает алгоритм, и она также выражается с помощью обозначения Big O .
Память – это большая тема, поэтому мы могли бы определить здесь некоторые базовые показатели. Предположим, что память – это место, или, точнее, слой, где хранятся все данные. Как? Что ж, есть следующие моменты:
- Данные, хранящиеся в памяти, хранятся в битах и байтах.
- Байты могут указывать на другие байты в памяти. (Со ссылкой на другие данные).
- Размеры байтов, например 4 байта или 8 байт в случае 32-разрядных или 64-разрядных целых чисел.
Обозначение Big O является наиболее важным инструментом для обобщения временной или пространственной сложности алгоритма. Эти значения не являются фиксированными, поэтому они могут варьироваться в зависимости от входных данных. Поэтому мы измеряем от наиболее производительного до наименее производительного как, O (1) как постоянную сложность, или O (log (n)), O (n), O (n ^ 2), O (n ^ 3) .. и т.д. и т.п.
Структуры данных обычно представлены в четырех формах:
- Линейные: массивы, списки.
- Дерево: двоичный файл, кучи, разделение пространства и т.д.
- Хэш: распределенная хэш-таблица, хэш-дерево и т.д.
- Графики: решающий, направленный, ациклический и т.д.
Имея эти инструменты, упомянутые и собранные в нашем “рюкзаке”, у нас есть практически все, что нужно для решения, определения, а затем написания наших алгоритмов наиболее эффективным способом для данного случая.
Как мы собираемся использовать все эти предметы, которые у нас есть в нашем “техническом рюкзаке”? Что ж, для начала нам нужна проблема. Справедливо, вот один из них, с которого легко начать.
Вот проблема из LeetCode . Именно то, что нам нужно.
Учитывая массив целых чисел nums и целочисленное целевое значение, верните индексы двух чисел таким образом, чтобы они складывались в target.
Вы можете предположить, что каждый ввод будет иметь ровно одно решение, и вы не можете использовать один и тот же элемент дважды.
Вы можете вернуть ответ в любом порядке.
Для примера:
Input: nums = [2,7,11,15], target = 9 Output: [0,1] Output: Because nums[0] + nums[1] == 9, we return [0, 1].
Теперь, когда мы поняли нашу проблему, мы будем радоваться. “Дааааа!!!” Мы знаем, как решить проблему, мы открываем наш “рюкзак” и выбираем наши инструменты.
class Solution {
public int[] twoSum(int[] nums, int target) {
for (int i = 0; i < nums.length -1; i++) {
int firstNumber = nums[i];
for (int j = i + 1; j < nums.length; j++) {
int secondNumber = nums[j];
if (firstNumber + secondNumber == target) {
return new int[] {firstNumber, secondNumber};
}
}
}
return new int[0];
}
}
“Ууууууу” , это работает!
Хммм… Да, это действительно работает, но поскольку мы новички на этом пути, мы использовали технику грубой силы , что означает, что мы проходили через наш массив с двумя целыми числами соответственно i и j , а затем мы попытались суммировать каждую комбинацию между ними. Поэтому мы использовали два вложенных цикла for для итерации по всему массиву. Поэтому мы использовали два вложенных цикла for для итерации по всему массиву. Большой O и его сложность во времени и пространстве? Хорошо, сложность пространства, которую мы имеем, равна O(1) . Великолепно, лучше и быть не может, постоянное пространство, что означает, что для хранения данных не использовалась дополнительная память. Итак, в итоге мы получаем O (n ^ 2) временную сложность. Причиной этого было повторение двух вложенных циклов в отношении, подводя итог, каждой комбинации. Что ж, мы должны сказать, что наш алгоритм кажется очень медленным. Что, если бы в нашем примере у нас был массив размером n вместо четырех целых чисел? Ну, это было бы очень медленно. Итак, можем ли мы сделать это лучше прямо сейчас?
Давайте попробуем еще раз.
class Solution {
public static int[] twoSum(int[] nums, int target) {
Set numbers = new HashSet<>();
for(int number : nums) {
int match = target - number;
if (numbers.contains(match)) {
return new int[] { match, number };
}
numbers.add(number);
}
return new int[0];
}
}
Это снова работает! Должен сказать, у нас все получается фантастически. Давайте еще раз поговорим с нашим Большим О другом. Теперь у нас ситуация немного лучше. Мы улучшили нашу временную сложность с O (n ^ 2) квадратичного времени до O (n) времени. Мы избавились от внутреннего цикла for и выполняем итерацию только один раз по всему массиву. Мы ввели структуру данных HashSet, и она помогает нам хранить потенциальные совпадающие комбинации, и после каждой итерации мы просматриваем хэш-таблицу, чтобы увидеть, суммировали ли мы целевое число. Намного быстрее, чем предыдущее решение. Мы значительно улучшили временную сложность, и теперь наш алгоритм работает намного быстрее. Однако, используя HashSet, мы выделили немного памяти. Помните, мы должны были где-то хранить наши совпадающие комбинации, и это означает, что наша сложность пространства уменьшилась. Это O(n) прямо сейчас, вместо O(1) в предыдущем примере.
Так каков же лучший подход сейчас?
Что ж, в первом примере у нас было O (n ^ 2) времени | O (1) сложность пространства, и теперь у нас есть O (n) время | O (n) сложность пространства. Я думаю, что мы улучшили наш алгоритм в целом. А теперь давайте посмотрим, сможем ли мы сделать еще лучше.
class Solution {
public static int[] twoSum(int[] nums, int target) {
Arrays.sort(nums);
int left = 0;
int right = nums.length - 1;
while (left < right) {
int sum = nums[left] + nums[right];
if (sum == target) {
return new int[] { nums[left], nums[right] };
} else if (sum < target) {
left++;
} else if (sum > target) {
right--;
}
}
return new int[0];
}
}
Третий раз успех! Изумительный маневр! Давай пойдем и поговорим там с нашим Большим другом О.
- Хорошо, Большой О , что у тебя есть для нас на этот раз?
- Что ж, у меня есть для тебя хорошие новости.
Возможно, мы знаем, что хороший алгоритм сортировки, такой как быстрая сортировка, сортировка слиянием или сортировка по куче, может выполняться за O(n *log(n)) время. Таким образом, это объясняет сортировку массива прямо сверху, а затем мы можем найти сумму в O (n) time, и мы не используем никакого дополнительного пространства, поэтому мы снова улучшили сложность пространства до O (1) . С помощью этой настройки нам разрешено делать следующее. Поскольку массив был немедленно отсортирован, мы, безусловно, можем поместить левый указатель в начало массива, а правый – в самый конец массива. Мы суммируем элементы в первом цикле и сравним, равна ли сумма целевому числу. В случае истины мы просто возвращаем позиции указателей, соответственно, если сумма меньше целевого числа, нам придется увеличить левый указатель на одну позицию, чтобы увеличить сумму указателей. Однако, если сумма больше целевого числа, это будет означать, что мы должны переместить правый указатель на одну позицию влево, чтобы уменьшить сумму указателей.
Подводя итог, мы сразу отсортировали массив, а затем провели итерацию один раз по всему массиву. Наконец, мы смогли найти наше третье решение за O(n* log(n)) время | O(1) сложность пространства. Это очень классное решение, но было ли оно лучше предыдущего? Ну, это зависит от того, каковы ваши потребности. Хотим ли мы больше заботиться о производительности сложности во времени или пространстве? Я просто позволю тебе решить самой.
Это была демонстрация того, как мы можем применять различные методы, память и структуры данных для написания эффективных алгоритмов. Мы начали с техники грубой силы, которая обычно является наименее производительной, а затем попытались понять, что может быть возможным улучшением, в поисках лучших инструментов внутри нашего “рюкзака”.
Мне нравится использовать это пошаговое решение “. Старайся совершенствоваться!” Старая пословица в столярном деле гласит: Измерь трижды, проверь дважды и Отрежь Один раз!
Оригинал: “https://dev.to/nemanyam/road-to-algorithm-world-4a19”