Изучение алгоритмов для массивов и строк: два указателя, скользящее окно и сумма префиксов

Массивы и строки являются фундаментальными структурами данных в информатике и программировании. Эффективное манипулирование и обработка этих типов данных имеет решающее значение для решения широкого круга задач. В этом посте для разработчиков мы рассмотрим три популярных алгоритмических метода работы с массивами и строками: Два указателя, Скользящее окно и Сумма префиксов. . Мы рассмотрим их концепции и предоставим примеры кода, иллюстрирующие их практическое применение. Но прежде чем мы начнем, нам нужно понять, почему мы используем эти понятия и что означает Big O Notation.

В программировании нотация Big O — это способ описания характеристик производительности алгоритма. Он дает оценку того, как время выполнения алгоритма или требования к пространству растут по мере увеличения размера входных данных. Обозначение Big O обычно используется для анализа временной и пространственной сложности алгоритмов.

  1. Временная сложность (обозначение Big O для времени выполнения). Временная сложность представляет собой количество времени, которое требуется алгоритму для выполнения, в зависимости от размера входных данных. Он описывает скорость роста времени выполнения алгоритма по отношению к размеру входных данных. Обозначение Big O обеспечивает верхнюю границу наихудшего сценария временной сложности алгоритма.

Вот некоторые часто встречающиеся временные сложности:

  • O(1) — Постоянное время: время выполнения алгоритма не зависит от размера входных данных. Он выполняет фиксированное количество операций независимо от размера ввода.
  • O(log n) — логарифмическое время: время выполнения алгоритма увеличивается логарифмически с размером входных данных. Примеры включают бинарный поиск или определенные алгоритмы «разделяй и властвуй».
  • O(n) — линейное время: время выполнения алгоритма увеличивается линейно с размером входных данных. Он выполняет постоянное количество операций для каждого элемента на входе.
  • O(n log n) — линейное арифмическое время: время выполнения алгоритма растет пропорционально размеру входных данных, умноженному на логарифм размера входных данных. Это часто встречается в эффективных алгоритмах сортировки, таких как сортировка слиянием или быстрая сортировка.
  • O(n²) — квадратичное время: время выполнения алгоритмаувеличивается квадратично с размером входных данных. Обычно это включает вложенные итерации по входным данным.
  • O(2^n) — экспоненциальное время: время выполнения алгоритма удваивается с каждым дополнительным входным элементом. Это обычно встречается в алгоритмах грубой силы или рекурсивных алгоритмах, которые исследуют все возможные комбинации.
  1. Пространственная сложность (обозначение 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.

Вот разбивка анализа временной сложности:

  1. Первый цикл for повторяется k раз, где k — размер окна. Поскольку k является постоянным значением, временная сложность этого цикла составляет O(1).
  2. Второй цикл for повторяется от k до nums.length - 1, то есть n - k итераций. Следовательно, временная сложность этого цикла равна O(n - k).
  3. Во втором цикле 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)

Заключение

Методы Два указателя, Скользящее окно и Сумма префиксов — мощные инструменты для решения алгоритмических задач, связанных с массивами и строками. Используя эти методы, разработчики могут повысить эффективность и результативность своих решений. Понимание этих концепций и их приложений может быть чрезвычайно ценным при решении широкого круга задач программирования.

Пожалуйста, не стесняйтесь экспериментировать и добавлять свои собственные примеры кода для дальнейшего изучения этих методов!