Изучение алгоритмов для массивов и строк: два указателя, скользящее окно и сумма префиксов
Массивы и строки являются фундаментальными структурами данных в информатике и программировании. Эффективное манипулирование и обработка этих типов данных имеет решающее значение для решения широкого круга задач. В этом посте для разработчиков мы рассмотрим три популярных алгоритмических метода работы с массивами и строками: Два указателя, Скользящее окно и Сумма префиксов. . Мы рассмотрим их концепции и предоставим примеры кода, иллюстрирующие их практическое применение. Но прежде чем мы начнем, нам нужно понять, почему мы используем эти понятия и что означает Big O Notation.
В программировании нотация Big O — это способ описания характеристик производительности алгоритма. Он дает оценку того, как время выполнения алгоритма или требования к пространству растут по мере увеличения размера входных данных. Обозначение Big O обычно используется для анализа временной и пространственной сложности алгоритмов.
- Временная сложность (обозначение Big O для времени выполнения). Временная сложность представляет собой количество времени, которое требуется алгоритму для выполнения, в зависимости от размера входных данных. Он описывает скорость роста времени выполнения алгоритма по отношению к размеру входных данных. Обозначение Big O обеспечивает верхнюю границу наихудшего сценария временной сложности алгоритма.
Вот некоторые часто встречающиеся временные сложности:
- O(1) — Постоянное время: время выполнения алгоритма не зависит от размера входных данных. Он выполняет фиксированное количество операций независимо от размера ввода.
- O(log n) — логарифмическое время: время выполнения алгоритма увеличивается логарифмически с размером входных данных. Примеры включают бинарный поиск или определенные алгоритмы «разделяй и властвуй».
- O(n) — линейное время: время выполнения алгоритма увеличивается линейно с размером входных данных. Он выполняет постоянное количество операций для каждого элемента на входе.
- O(n log n) — линейное арифмическое время: время выполнения алгоритма растет пропорционально размеру входных данных, умноженному на логарифм размера входных данных. Это часто встречается в эффективных алгоритмах сортировки, таких как сортировка слиянием или быстрая сортировка.
- O(n²) — квадратичное время: время выполнения алгоритмаувеличивается квадратично с размером входных данных. Обычно это включает вложенные итерации по входным данным.
- O(2^n) — экспоненциальное время: время выполнения алгоритма удваивается с каждым дополнительным входным элементом. Это обычно встречается в алгоритмах грубой силы или рекурсивных алгоритмах, которые исследуют все возможные комбинации.
- Пространственная сложность (обозначение Big O для использования памяти). Пространственная сложность измеряет объем памяти, требуемый алгоритмом, в зависимости от размера входных данных. Он описывает скорость роста использования памяти алгоритмом по отношению к размеру входных данных. Подобно временной сложности, нотация Big O обеспечивает верхнюю границу наихудшего сценария пространственной сложности алгоритма.
Общие космические сложности включают в себя:
- O(1) — постоянное пространство: алгоритм использует фиксированный объем памяти, который не зависит от размера входных данных.
- O(n) — линейное пространство: использование памяти алгоритмомувеличивается линейно с размером входных данных.
- O(n²) — квадратичное пространство: использование памяти алгоритмом указывает квадратичное соотношение строк с входным размером.
Стоит отметить, что пространственная сложность также может зависеть от таких факторов, как вспомогательные структуры данных, используемые в алгоритме, или глубина рекурсии в рекурсивных алгоритмах.
Понимание временной и пространственной сложности алгоритма имеет решающее значение для оценки его эффективности, масштабируемости и потенциальных проблем с производительностью. Анализируя эти сложности, разработчики могут принимать обоснованные решения о выборе алгоритма, оптимизации и компромиссах в своем коде.
Техника двух указателей обычно используется для решения проблем, связанных с массивами или строками, путем поддержки двух указателей, которые определенным образом перемещаются по структуре данных. Этот метод особенно полезен при работе с отсортированными массивами или при поиске пар или подмассивов с определенными свойствами.
function reverseString(s: string[]): void { let left: number = 0; for (let right = s.length - 1; right >= left; right--) { let temp: string = s[left]; // declaring a variable to memorize left value before it is changed s[left] = s[right]; s[right] = temp; left++; } }
В этом фрагменте кода функция reverseString
принимает массив строк (s
) в качестве входных данных и использует два указателя, left
и right
, для перестановки элементов из начала и конца массива. Увеличивая left
и уменьшая right
на каждой итерации, функция эффективно меняет порядок элементов в массиве на противоположный.
Этот подход имеет временную сложность O (n), поскольку он выполняет линейное сканирование массива.
Техника скользящего окна полезна для решения задач, связанных с поиском или обработкой подмассивов или подстрок заданного массива или строки. Он включает в себя поддержку «окна» или подмассива/подстроки, которые динамически регулируют свой размер при перемещении по структуре данных.
function findMaxAverage(nums: number[], k: number): number { let ans = 0; let curr = 0; // k is a fixed window size for (let i = 0; i < k; i++) { curr += nums[i]; } ans = curr; for (let i = k; i < nums.length; i++) { curr += nums[i] - nums[i - k]; ans = Math.max(ans, curr); // here we iterating over all subarrays with size k in array } return ans / k; }
В этом фрагменте кода функция findMaxAverage
принимает в качестве входных данных массив чисел (nums
) и размер окна (k
). Он использует метод скользящего окна для вычисления максимального среднего подмассива длиной k
. Сохраняя текущую сумму (curr
) и обновляя ее по мере того, как окно скользит по массиву, функция находит максимальную сумму и делит ее на k
, чтобы получить максимальное среднее значение.
Временная сложность данного кода равна O(n), где n — длина массива nums
.
Вот разбивка анализа временной сложности:
- Первый цикл
for
повторяетсяk
раз, гдеk
— размер окна. Посколькуk
является постоянным значением, временная сложность этого цикла составляет O(1). - Второй цикл
for
повторяется отk
доnums.length - 1
, то есть n - k итераций. Следовательно, временная сложность этого цикла равна O(n - k). - Во втором цикле
for
каждая итерация выполняет операции с постоянным временем, такие как сложение, вычитание и сравнение. Следовательно, временная сложность операций внутри цикла равна O(1).
Следовательно, временная сложность данного кода равна O(n).
Техника суммы префиксов часто используется при кумулятивных вычислениях или поиске подмассивов с определенными свойствами. Он включает предварительное вычисление и сохранение сумм префиксов, которые представляют собой кумулятивные суммы элементов до определенного индекса в массиве или строке.
function runningSum(nums: number[]): number[] { let prefix = [nums[0]]; for (let i = 1; i < nums.length; i++) { prefix.push(nums[i] + prefix[prefix.length - 1]); // adding new value with previous prefix sum } return prefix; }
В этом фрагменте кода функция runningSum
принимает массив чисел (nums
) в качестве входных данных и вычисляет текущую сумму, используя технику суммы префиксов. Он перебирает массив, добавляя текущий элемент к последнему элементу в массиве prefix
, и добавляет результат в массив prefix
. Функция возвращает результирующий массив суммы префиксов.
В целом доминирующим фактором временной сложности является цикл for
, который имеет временную сложность O(n)
Заключение
Методы Два указателя, Скользящее окно и Сумма префиксов — мощные инструменты для решения алгоритмических задач, связанных с массивами и строками. Используя эти методы, разработчики могут повысить эффективность и результативность своих решений. Понимание этих концепций и их приложений может быть чрезвычайно ценным при решении широкого круга задач программирования.
Пожалуйста, не стесняйтесь экспериментировать и добавлять свои собственные примеры кода для дальнейшего изучения этих методов!