Изучение алгоритмической парадигмы для решения задач в линейном времени: O (N).
Если вы пытались решить проблемы конкурентного кодирования и думали, что было бы легко, если бы мы могли идентифицировать шаблоны или парадигму мышления для данной проблемы и иметь возможность расширять или повторно использовать ее для решения других проблем - тогда эта серия для вас!
В своем первом блоге я хочу осветить метод решения определенного класса задач в «линейном времени выполнения».
Подробнее о временной сложности в алгоритмах - отметьте: this
Итак, что на самом деле означает линейное время?
Временная сложность O () или нотация Big O используются для обозначения «верхней границы» времени обработки алгоритма. Если у вас есть «N» элементов данных, и вы посещаете или проверяете каждый элемент данных «не более одного раза», прежде чем прийти к выводу / решению, то считается, что алгоритм занимает O (N) времени. Это означает, что чем больше элементов, тем больше требуется времени на обработку - и оно растет линейно с количеством элементов!
Итак, без лишних слов, я хочу провести вас через все и помочь вам раскрыть основную идею решения определенного класса задач в линейном времени - используя то, что я люблю называть техникой «бухгалтерского учета».
Что такое бухгалтерия?
Это просто означает использование переменных, чтобы помочь нам запомнить или отметить соответствующие промежуточные данные, которые потенциально могут быть кандидатами или помочь нам прийти к окончательному решению, которое мы ищем при решении данной проблемы. Мы также столкнемся с этим при рассмотрении других парадигм алгоритмов, таких как динамическое программирование, где процесс запоминания промежуточных результатов называется «мемоизацией».
Как это помогает?
В классе задач, которые мы собираемся рассмотреть, этот метод бухгалтерского учета поможет сократить алгоритм O (N²) или O (N log N) до линейного времени O (N).
Давайте сразу перейдем к примеру проблемы, чтобы понять, на что я намекаю.
Задача 01 - Нахождение сделки« одна покупка и одна продажа », установленная для получения максимальной прибыли:
Требование. Допустим, у вас есть массив, в котором i-й элемент представляет собой цену данной акции на i-й день. Если вам было разрешено совершить не более одной транзакции (т. Е. Купить одну и продать одну акцию), разработайте алгоритм для определения максимальной прибыли.
Теперь предположим, что данные представлены в виде массива цен [N]. Чтобы получить прибыль, действие покупки должно происходить перед опционом на продажу.
При указанном выше условии, если каждый элемент price [i], i = 0..N-2 рассматривается как подходящий вариант ПОКУПКА, тогда цены [j] потенциально могут быть ПРОДАЖА вариант, j = 1..N-1.
Найти: Макс. Прибыль = Макс. (Цены [j] -цены [i]) для i = 0..N-2, j = 1..N-1
Среди этих вариантов, поскольку нам нужно найти только одну пару значений ПОКУПКИ и одну ПРОДАЖУ, которая дает максимальную прибыль, т. Е. Нам нужно получить максимальную разницу цен [j] - цен [i], для некоторые j ›i.
Эта мысль приводит нас к своего рода способу решения этой проблемы с помощью метода грубой силы - т. Е. Просматривать или проверять каждый элемент в price [i] и сравнивать с ценами [i + 1] через цены [N-1 ] по каждому индексу i - найти максимально возможную прибыль.
int maxProfit(vector<int>& prices) {
int i=0;
int j=0;
int profit= 0;
int size = prices.size();
// traverse the prices looking for maximum profit seen
for(i=0;i<size-1;i++){
j=i+1;
while(j<size)
// Find if we can get new profit from value at prices[i]
if((prices[j]-prices[i])>profit){
profit= prices[j]-prices[i];
}
j++;
}
}
return profit;
}
Ясно, что здесь мы видим два цикла - следовательно, алгоритм дает O (N²)!
Теперь, можем ли мы сделать лучше?
Что нам действительно нужно, чтобы получить максимальную прибыль?
Нам нужно найти одно минимальное значение (- такое, по которому мы могли бы купить), и нам нужно найти одно максимальное значение, которое возникает после минимального значения (- которое мы могли бы продать по ).
Итак, в каждой точке все, что нам нужно отметить, это:
[a] какой минимум мы видели до сих пор и может ли это значение заменить текущий минимум?
[b] А что, если мы продадим по этой цене - принесет ли это нам максимальную прибыль?
По сути, это всего лишь две проверки условий, пока мы просматриваем массив данных.
Таким образом, мы можем получить максимальную прибыль за время O (N) и использовать постоянное пространство - всего две бухгалтерские переменные, как в приведенном ниже коде.
int maxProfit(vector<int>& prices) {
int size = prices.size();
int i=0;
// bookkeeping variables
int min_price = INT_MAX;
int profit = 0;
// all we need to do is to update bookkeeping variables as we
// traverse the input data
for(i=0; i<size; i++){
min_price = ((prices[i]<min_price)?prices[i]:min_price);
profit = (((prices[i]-min_price)>profit)?(prices[i]-\
min_price):profit);
}
return profit;
}
Вы спросите, какова временная эффективность этого алгоритма? Картинка говорит тысячу слов;)… Итак, поехали!
А теперь почему бы нам не распространить это мышление на еще несколько проблем, приведенных ниже. [Чтобы решить их за O (N) время выполнения]
- Найдите максимальное значение в заданном несортированном массиве.
- Найдите минимальное значение в заданном несортированном массиве.
- Найдите два числа или их индексы в несортированном массиве, которые складываются в сумму s.
- Найдите в массиве два числа, разность которых равна «d».
Вот несколько советов:
Подумайте о способе обойти массив только один раз.
Сохраняйте / используйте бухгалтерские переменные при обходе массива, отмечая промежуточный результат или значения, которые могут помочь вам прийти к решению!
Поиск максимального / минимального значения в несортированном массиве
Как насчет - Обход массива только один раз при обновлении бухгалтерской переменной «max_value» или «min_value» для каждого индекса. Вуаля! O (N) и также не нужно сортировать массив!
int findMax(vector<int>& data){
// initial value can't be zero, since integer array
// can have negative numbers
int max = INT_MIN;
int i = 0;
// Let's traverse array only once, looking for what we want
// at each element check if can be made the new max.
for(i=0;i<data.size();i++){
if(data[i]>max){
max = data[i];
}
}
return max;
}
Поиск любых двух целых чисел или индексов элементов данных, которые в сумме дают заданное значение «сумма» в несортированном массиве - data []
сумма = данные [i] + данные [j] и (i! = j)
Методом грубой силы - по каждому индексу i мы проверяем, содержат ли остальные значения массива «впереди» значение, которое может дать требуемую сумму - при добавлении значения в i - данные [i]. По сути, это приводит к алгоритму O (n²), поскольку для каждого значения в i мы проверяем все значения от (i + 1) до (N-1), чтобы найти соответствующий номер пары, который может дать заданную сумму - требуя двух циклов обработка!
Теперь подумайте, что вы можете запомнить и использовать позже, чтобы найти ответ на вашу проблему.
Что, если бы мы вспомнили все ценности, которые видели до сих пор? Мы смотрим ~ назад ~ (а не вперед, как в грубой силе)
[скажем, используя карту чисел и ее индекс]
Затем для каждого индекса j все, что нам нужно сделать, это -
Найдите данные кандидата [i] на карте наблюдаемых значений, чтобы
data [i] = (sum- data [j])… (i)
Используйте немного дополнительной памяти, чтобы повысить эффективность работы!
vector<int> findNumsWithSum(vector<int>& data, int sum){
int i = 0;
int map<int,int> numIndexMap;
for(i=0;i<data.size();i++){
// find number we can add to data[i] to form sum.
int num_to_find= sum - data[i];
// check if we have seen a number before that can form the sum
// with number data[i] at index 'i',
if(numIndexMap.find(num_to_find) != numIndexMap.end()){
// you can return integers or indices here.
// In this example, we are returning integer values.
return {(numIndexMap.find(num_to_find)->first),data[i]};
}
//add this number to seen map
numIndexMap[data[i]]=i;
}
//could not find such a pair, return {0,0}
return {};
}
Вы снова сказали, какова эффективность? Это О (Н), ага !!
Ну вот :
Надеюсь, этот простой метод поможет вам решить больше подобных задач за «линейное время». Сообщите мне, помогло ли это вам!
Кроме того, еще несколько проблем, прежде чем я уйду -
A. Ваш браслет для фитнес-трекера измеряет ваш уровень роста в течение дня, сообщая значения N в разное время. Можете ли вы найти максимальное увеличение высоты за день - за O (N) времени?
Б. Также, можете ли вы найти три числа в массиве, сумма которого равна «сумме».
