Вам не нужно быть математическим гением, чтобы быть хорошим программистом, но есть приемы, которые вы можете добавить в свой пакет решения проблем, чтобы улучшить производительность ваших алгоритмов и произвести впечатление на технических собеседованиях. В этом уроке вы узнаете, как сложить ряд последовательных целых чисел от 1 до n с помощью простого и легко запоминающегося уравнения. Это уравнение полезно для рефакторинга функции от сложности O(n) до O(1).
Я считаю, что 90% людей будут арифметической прогрессией, но 50% людей будут думать об обходе цикла, когда увидят сумму от 1 до n, и еще меньше людей будут учитывать сложность алгоритма.
1 Как вычислить сумму от 1 до n
Как вы складываете числа?
[1,2,3,4,5,6,7,8,9,10]
Была ли ваша первая мысль подходом «грубой силы»?
1 + 2 = 3
3 + 3 = 6
6 + 4 = 10
10 + 5 = 15
15 + 6 = 21
21 + 7 = 28
28 + 8 = 36
36 + 9 = 45
45 + 10 = 55
Это нормально, вам, вероятно, не нужна ручка или калькулятор, чтобы добраться туда. Что если массив содержит 100, 1000 или 1 000 000 элементов?
2 реализация кода
Мы можем легко написать цикл for для автоматического добавления нашей серии:
const nums = [1,2,3,4,5,6,7,8,9,10];
const sumHarder = arr => {
let sum = 0;
for (let i = 0; i < arr.length; i++) {
sum += arr[i];
}
return sum;
}
const result = sumHarder(nums);
Чтобы быть немного более элегантным, вы можете использовать сокращение
const nums = [1,2,3,4,5,6,7,8,9,10];
const x = nums.reduce((a,b) => a+b);
Это решает задачу суммирования.
- Какова сложность приведенного выше алгоритма?
- O(n).
Зачем?
Наша функция должна выполнять операцию на каждом входе, поэтому порядок нашего алгоритма равен O(n) или линейной временной сложности.
Должен быть лучший способ!
Вместо того, чтобы решать ее с помощью грубой силы, давайте посмотрим, как решить эту проблему с помощью алгоритма?
Взгляните еще раз на наш массив. Можно ли найти сумму каким-либо другим способом?
[1,2,3,4,5,6,7,8,9,10]
Когда вы подводите итог, вы, вероятно, начинаете с одного конца и продвигаетесь к другому.
Или вы можете начать с конца и работать в обратном порядке, например:
10 + 9 = 19
19 + 8 = 27
27 + 7 = 34
34 + 6 = 40
40 + 5 = 45
45 + 4 = 49
49 + 3 = 52
53 + 2 = 54
54 + 1 = 55
Если мы начнем накапливать фронт и начнем накапливать зад, каков будет результат?
Заметили что-нибудь?
Если мы просуммируем сумму каждой строки в таблице, мы получим число, кратное 11.
Интересно, а если начать с концов и постепенно переходить к середине?
1 + 10 = 11
2 + 9 = 11
3 + 8 = 11
4 + 7 = 11
5 + 6 = 11
Видишь узор?
У нас есть пять пар, по 11 в каждой. Произведение этих пар равно 55.
Но как выполнить этот расчет, если длина массива неизвестна?
Мы по-прежнему будем создавать пары, но будем использовать переменную n в качестве заполнителя для длины массива.
1 + n = (n + 1)
2 + n -1 = (n + 1)
……
Сопоставляет второй элемент массива с предпоследним элементом. Второй элемент равен 2. Предпоследний элемент — это длина массива минус 1, так что это n-1.
Какова сумма 2 + n -1?
n+1
тогда мы продолжаем
3 + n - 2 = n + 1
4 + n - 3 = n + 1
5 + n - 4 = n + 1
В какой-то момент мы достигнем медианы массива. Это значение равно n/2. Медиана равна 5, что представляет собой частное 10, деленное на 2.
Чему равно n / 2 * (n + 1)?
n ( n + 1) / 2
Ну, мы нашли вышеуказанное правило, тогда подставим 10 в вышеприведенное уравнение.
10 ( 10 + 1) / 2 = 55
Отлично! Мы получили желаемый результат.
но!
Это отлично работает, если длина массива четная. Но что, если это нечетное число? Что, если наш массив содержит нечетное количество элементов? Вот так:
[1,2,3,4,5,6,7,8,9]
Мы рисуем высокое и низкое значение в соответствии с приведенной выше процедурой, мы найдем одинокую медиану.
1 + 9 = 10
2 + 8 = 10
3 + 7 = 10
4 + 6 = 10
5
Что такое 5? Это половина суммы нашего права. Другими словами, медиана равна половине суммы n + 1.
Мы можем записать это как уравнение для определения медианы:
(n + 1) / 2
Это выглядит знакомо? Если мы знаем медиану, каков следующий шаг?
Нам просто нужно умножить это значение на длину массива.
n(n + 1) / 2
Этот массив можно использовать для решения задач суммирования независимо от длины массива.Это уравнение очень полезно для повышения эффективности нашего алгоритма.
Давайте посмотрим на вышеуказанную функцию. Как мы восстанавливаем это, чтобы улучшить его сложность алгоритма?
Нам просто нужно преобразовать уравнение в JavaScript!
const sumSmarter = arr =>
arr.length * (arr.length + 1)/2;
Алгоритмическая сложность приведенной выше функции снижена до O(1), наша функция всегда выполняет одно и то же количество операций независимо от длины массива.
3 Как вычислить сумму от 1 до n
В этом уроке вы узнали, как суммировать ряд последовательных целых чисел с помощью простого и легко запоминающегося уравнения.
Когда мы брали интервью, интервьюер время от времени спрашивал, пожалуйста, напишите сумму от 1 до 100. Благодаря приведенному выше объяснению, я полагаю, вы, по крайней мере, знаете, как уменьшить сложность алгоритма.
В повседневном кодировании мы можем использовать некоторые правила и формулы, чтобы уменьшить сложность алгоритма. Давайте воспользуемся этим.
翻译原文地址: [https://dev.to/nielsenjared/improve-your-algorithms-with-this-simple-equation-3g1c]
наконец
- Добро пожаловать в «Front-end Jiajia» и регулярно делитесь высококачественными статьями.
- Ответьте, чтобы добавить группу, пригласите вас присоединиться к технической группе, долгосрочному техническому обмену и обучению