Как работают алгоритмы
Chapter 8 Algorithm Analysis Techniques

Глава 8: Методы анализа алгоритмов

В предыдущих главах мы исследовали широкий спектр основных алгоритмов и структур данных, охватывая такие темы, как сортировка, поиск, графы, строки и различные приложения. Хотя реализация и понимание этих алгоритмов имеют решающее значение, не менее важно анализировать их характеристики производительности, чтобы принимать обоснованные решения при выборе алгоритмов для конкретных задач. В этой главе мы углубимся в методы, используемые для анализа и оценки алгоритмов, сосредоточившись на математических моделях, эмпирических исследованиях и визуализации алгоритмов.

Математические модели и анализ

Математический анализ является мощным инструментом для понимания поведения и производительности алгоритмов. Разрабатывая математические модели, которые отражают основные характеристики алгоритма, мы можем рассуждать об его эффективности и масштабируемости. Эти модели позволяют нам делать прогнозы о времени выполнения алгоритма, использовании памяти и других показателях производительности, что позволяет нам сравнивать различные алгоритмы и выбирать наиболее подходящий для конкретной задачи.

Обозначение Большое-O

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

В обозначении Большое-O мы выражаем производительность алгоритма как функцию от размера входных данных, обычно обозначаемую как n. Например, рассмотрим следующую простую функцию, которая вычисляет сумму первых n положительных целых чисел:

public static int sum(int n) {
    int sum = 0;
    for (int i = 1; i <= n; i++) {
        sum += i;
    }
    return sum;
}

Время выполнения этой функции растет линейно с размером входных данных n. Мы можем выразить это, используя обозначение Большое-O как O(n), указывая, что время выполнения пропорционально размеру входных данных. Это означает, что по мере увеличения размера входных данных, время выполнения алгоритма также будет увеличиваться пропорционально.Вот перевод на русский язык:

Когда размер входных данных увеличивается, время выполнения алгоритма увеличивается не более чем линейно.

Обозначение Big-O позволяет нам игнорировать постоянные факторы и члены низшего порядка, сосредоточившись на доминирующем члене, который определяет темп роста функции. Например, рассмотрим следующую функцию:

public static int sumOfSquares(int n) {
    int sum = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= i; j++) {
            // Суммируем квадраты чисел от 1 до n
            sum += j;
        }
    }
    return sum;
}

Время выполнения этой функции пропорционально квадрату N. Точнее, количество раз, когда выполняется оператор sum += j, равно 1 + 2 + ... + N ~ N^2/2.

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

Алгоритм Кнута-Морриса-Пратта

Алгоритм Кнута-Морриса-Пратта (KMP) является эффективным алгоритмом поиска подстроки, который использует предварительно вычисленную "функцию сбоя" для избежания ненужных сравнений.

Функция сбоя сообщает нам длину самого длинного правильного префикса образца, который также является суффиксом подстроки образца, которую мы уже сопоставили. Это позволяет нам "перепрыгивать" в тексте, когда мы находим несоответствие, вместо того, чтобы возвращаться назад.

Вот пример работы алгоритма KMP:

Текст:    "abacadabrabracabracadabrabrabracad"
Образец: "abracadabra"
Вывод:  [13]

Алгоритм KMP имеет время выполнения O(n + m), что делает его гораздо более эффективным, чем грубый подход, для больших текстов и образцов.

Алгоритм Бойера-Мура

Алгоритм Бойера-Мура - это еще один эффективный алгоритм поиска подстроки, который работает путем предварительной обработки строки образца. В отличие от KMP, который начинает сравнения с начала образца, Бойер-Мур начинает с конца и работает в обратном направлении.

Ключевая идея Бойера-Мура заключается в использовании двух предварительно вычисленных функций: "хорошего суффикса"Вот перевод на русский язык с сохранением кода:

Функция "хорошего символа" и функция "плохого символа". Эти функции позволяют нам пропускать вперед в тексте, когда мы находим несоответствие, аналогично алгоритму Кнута-Морриса-Пратта.

Вот пример алгоритма Бойера-Мура:

Текст:    "abacadabrabracabracadabrabrabracad"
Шаблон: "abracadabra"
Вывод:  [13]

Бойер-Мур имеет лучший случай времени выполнения O(n/m) и худший случай времени выполнения O(n * m), но на практике он часто является самым быстрым алгоритмом поиска подстроки для больших алфавитов.

Регулярные выражения

Регулярные выражения - это мощный инструмент для описания шаблонов в строках. Они предоставляют лаконичную и гибкую нотацию для сопоставления, поиска и манипулирования текстом.

Регулярное выражение - это последовательность символов, определяющая шаблон поиска. Простейшая форма регулярного выражения - это буквальная строка, такая как "hello", которая точно соответствует строке "hello". Однако регулярные выражения также включают специальные символы и конструкции, позволяющие создавать более сложные шаблоны:

  • . (точка) соответствует любому одиночному символу.
  • * (звездочка) соответствует нулю или более вхождениям предыдущего символа или группы.
  • + (плюс) соответствует одному или более вхождениям предыдущего символа или группы.
  • ? (вопросительный знак) соответствует нулю или одному вхождению предыдущего символа или группы.
  • ^ (каретка) соответствует началу строки.
  • $ (доллар) соответствует концу строки.
  • [] (квадратные скобки) определяют класс символов, соответствующих любому одиночному символу внутри скобок.

Вот несколько примеров регулярных выражений и шаблонов, которым они соответствуют:

  • a.b соответствует любой трехсимвольной строке, начинающейся с "a" и заканчивающейся на "b", такой как "acb", "a5b" или "a b".
  • a*b соответствует любой строке, состоящей из нуля или более символов "a", за которыми следует один символ "b", такой как "b", "ab", "aab" или "aaab".
  • a+b соответствует любой строке, состоящей из одного или более символов "a", за которыми следует один символ "b", такой как "ab", "aab" или "aaab", но не "b".
  • a?b соответствует либо "ab", либо "b".
  • ^a соответствует любой строке, начинающейся с "a".Вот перевод файла на русский язык с сохранением кода:

ts с "a".

  • a$ соответствует любой строке, которая заканчивается на "a".
  • [aeiou] соответствует любому одиночному гласному символу.

Регулярные выражения поддерживаются многими языками программирования и инструментами, включая Java, Python и Unix-утилиты, такие как grep и sed. Они широко используются для задач, таких как проверка данных, обработка текста и анализ журналов.

Сжатие данных

Сжатие данных - это процесс кодирования информации с использованием меньшего количества битов, чем оригинальное представление. Это полезно для уменьшения требований к хранению и времени передачи. Существует два основных типа сжатия: без потерь и с потерями. Сжатие без потерь позволяет полностью восстановить исходные данные из сжатых данных, в то время как сжатие с потерями допускает некоторую потерю информации в обмен на более высокие коэффициенты сжатия.

Кодирование длин серий

Кодирование длин серий (RLE) - это простая техника сжатия без потерь, которая заменяет повторяющиеся последовательности одинаковых символов (серии) одним экземпляром символа и подсчетом количества его повторений.

Вот пример RLE:

Ввод:  "AAAABBBCCCDDDEEE"
Вывод: "4A3B3C3D3E"

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

Кодирование Хаффмана

Кодирование Хаффмана - это алгоритм сжатия без потерь, который присваивает переменную длину кодов символам в зависимости от их частоты в исходных данных. Более частые символы получают более короткие коды, а менее частые символы - более длинные коды.

Алгоритм работает, построив двоичное дерево, называемое деревом Хаффмана, снизу вверх. Каждый листовой узел представляет символ и его частоту, а каждый внутренний узел представляет сумму частот его дочерних узлов. Дерево строится путем повторного объединения двух узлов с наименьшими частотами, пока не останется только один узел.

После построения дерева код для каждого символа определяется путем от корня доВот русский перевод этого файла Markdown. Для кода я не переводил код, а только комментарии.

Вот пример кодирования Хаффмана:

Входные данные: "AAAABBBCCCDDDEEE" Выходные данные: "000010011001011100101"

Дерево Хаффмана: (15) /
(7) (8) / \ /
(4) (3) (3) (5) /\ /\ /\ /
A B C D E


В этом примере "A" получает код "00", "B" получает "01", "C" получает "10", "D" получает "110", а "E" получает "111". Сжатый вывод получается путем замены каждого символа во входных данных его соответствующим кодом.

Кодирование Хаффмана является оптимальным префиксным кодом, что означает, что ни один код не является префиксом другого кода. Это позволяет однозначно декодировать сжатые данные. Кодирование Хаффмана широко используется в различных форматах файлов и инструментах сжатия, таких как JPEG, MP3 и ZIP.

### Сжатие Lempel-Ziv-Welch (LZW)

Сжатие Lempel-Ziv-Welch (LZW) - это алгоритм сжатия на основе словаря, который строит словарь (или кодовую книгу) строк во время сжатия входных данных. LZW широко используется в утилитах сжатия файлов и использовался в формате изображений GIF.

Основная идея LZW заключается в замене строк символов одиночными кодами. Он читает входную строку символ за символом и кодирует строку в компактное представление, заменяя каждый фиксированный код переменной длины. Чем длиннее строка, тем больше места экономится при ее кодировании в виде одного числа.

Вот пошаговое описание того, как работает сжатие LZW:

1. Инициализируйте словарь, чтобы он содержал все строки из одного символа.
2. Найдите самую длинную строку W в словаре, которая соответствует текущему вводу.
3. Выведите индекс словаря для W в выходные данные и удалите W из ввода.
4. Добавьте W, за которым следует следующий символ во входе, в словарь.
5. Перейдите к шагу 2.

Рассмотрим пример. Предположим, мы хотим сжать строку "ABABABABA" с помощью LZW.

1. Инициализируйте словарь, чтобы он содержал "A" и "B".
2. Самое длинное совпадение - "A". Выведите его индекс в выходные данные и удалите его из ввода.
3. Добавьте "A" + следующий символ "B" в словарь.
4. Перейдите к шагу 2.
```Вот перевод на русский язык с сохранением оригинального кода:

# Строковая обработка

## Сжатие данных с помощью LZW

Рассмотрим пример сжатия строки "ABABABABA" с помощью алгоритма LZW:

1. Инициализируем словарь, содержащий все одиночные символы. Словарь теперь содержит "A", "B" и "AB".
2. Самое длинное совпадение - "B". Выводим его индекс (1) и удаляем из входных данных. Словарь теперь содержит "A", "B", "AB" и "BA".
3. Самое длинное совпадение - "AB". Выводим его индекс (2) и удаляем из входных данных. Словарь теперь содержит "A", "B", "AB", "BA" и "ABA".
4. Самое длинное совпадение - "ABA". Выводим его индекс (4) и удаляем из входных данных. Словарь теперь содержит "A", "B", "AB", "BA", "ABA" и "ABAB".
5. Самое длинное совпадение - "BA". Выводим его индекс (3). Входные данные теперь пусты.

Сжатое представление "ABABABABA" - это последовательность индексов [1], которая требует меньше бит для представления, чем исходное ASCII-представление.

Декомпрессия работает аналогично, но в обратном порядке:

1. Инициализируем словарь, содержащий все одиночные символы.
2. Считываем код X из входных данных.
3. Выводим строку для X из словаря.
4. Если предыдущий код существует, добавляем предыдущую строку, конкатенированную с первым символом строки для X, в словарь.
5. Переходим к Шагу 2.

Сжатие LZW простое и быстрое, что делает его хорошим выбором для многих приложений. Однако у него есть некоторые ограничения. Размер словаря может значительно увеличиваться, потребляя большое количество памяти. Кроме того, словарь сбрасывается после каждого блока входных данных, что может снизить коэффициент сжатия для небольших файлов.

Несмотря на эти ограничения, LZW остается популярным и эффективным алгоритмом сжатия, особенно для приложений, где скорость важнее, чем достижение максимально возможного коэффициента сжатия.

## Заключение

В этой главе мы исследовали несколько важных алгоритмов обработки строк, включая сортировку строк, деревья поиска, поиск подстрок, регулярные выражения и сжатие данных. Эти алгоритмы лежат в основе многих реальных приложений и являются важными инструментами для любого программиста, работающего с текстовыми данными.

Мы начали с обсуждения сортировки строк, которая является...Вот перевод на русский язык:

Оптимизированные алгоритмы сортировки, которые используют специальные свойства строк. Сортировка с помощью индексированного подсчета, LSD-сортировка и MSD-сортировка предоставляют эффективные методы для сортировки строк на основе их отдельных символов.

Далее мы рассмотрели деревья-tries, древовидную структуру данных для хранения и извлечения строк. Деревья-tries позволяют быстро выполнять поиск по префиксу и широко используются в таких приложениях, как автозаполнение и таблицы маршрутизации IP.

Алгоритмы поиска подстрок, такие как алгоритмы Кнута-Морриса-Пратта и Бойера-Мура, позволяют нам эффективно искать шаблоны в более крупных строках. Эти алгоритмы имеют многочисленные применения в текстовых редакторах, вычислительной биологии и информационном поиске.

Регулярные выражения предоставляют мощный и гибкий способ описания шаблонов строк. Мы обсудили основной синтаксис регулярных выражений и то, как они могут использоваться для сопоставления с шаблонами и манипулирования строками в различных языках программирования и инструментах.

Наконец, мы исследовали алгоритмы сжатия данных, которые уменьшают размер данных, используя избыточность и шаблоны во входных данных. Мы рассмотрели кодирование длин серий, кодирование Хаффмана и сжатие Лемпеля-Зива-Велча, каждое из которых имеет свои сильные стороны и применения.

Понимание этих алгоритмов и структур данных для обработки строк имеет решающее значение для любого, кто работает с текстовыми данными. По мере того, как количество неструктурированных данных продолжает расти, способность эффективно манипулировать, искать и сжимать строки будет становиться все более ценной. Овладев техниками, рассмотренными в этой главе, вы будете хорошо подготовлены к решению широкого спектра задач по обработке строк в ваших собственных проектах и приложениях.
Chapter 7 ContextChapter 9 Algorithm Design Paradigms Divide and Conquer