Пример с определением анаграммы¶

Решение 1: Метки¶

Наше первое решение задачи про анаграмму будет проверять, входит ли каждый из символов первой строки во вторую. Если все символы будут “отмечены”, то строки являются анаграммами. “Пометка” символа будет выполняться с помощью замены его на специальное значение Python None. Однако, поскольку строки в Python иммутабельны, первым шагом обработки будет конвертирование второй строки в список. Каждый символ из первой строки может быть сверен с элементами списка и, если будет найден, отмечен оговоренной заменой. ActiveCode 4 демонстрирует эту функцию.

При анализе алгоритма нам стоит отметить, что каждый из n символов в s1 вызовет цикл по n символам списка, полученного из s2. Каждая из n позиций списка будет посещена единожды, чтобы проверить её на соответствие s1. Количество таких посещений будет выражено через сумму целых чисел от 1 до n. Ранее мы уже говорили, что это может быть записано как

С увеличением \(n\) слагаемое \(n^{2}\) начнёт доминировать, так что \(n\) и \(\frac {1}{2}\) можно проигнорировать. Таким образом, решение является \(O(n^{2})\)

Решение 2: Сортируй и сравнивай¶

Следующие решение задачи про анаграммы будет использовать тот факт, что даже если s1 и s2 различны, они будут анаграммами только если состоят из одинаковых символов. Следовательно, если мы отсортируем каждую строку в алфавитном порядке от a до z, то в итоге получим одинаковые строки (если, конечно, s1 и s2 - анаграммы). Это решение показано в ActiveCode 5. Опять же, в Python мы можем использовать встроенный метод sort, для списков, полученных в начале функции конвертацией каждой строки.

В первый момент вы можете подумать, что этот алгоритм имеет \(O(n)\), поскольку у него есть всего одна простая итерация для сравнения n символов после сортировки. Однако, два вызова Python-метода sort не проходят даром. Как мы увидим в следующих главах, сортировка обычно имеет \(O(n^{2})\) или \(O(n\log n)\), так что эта операция доминирует над циклом. В итоге алгоритм будет иметь тот же порядок операций, что и сортировочные вычисления.

Решение 3: Полный перебор¶

Техника полного перебора для решения задач обычно используется, когда все другие возможности уже исчерпаны. Для задачи определения анаграммы мы можем просто сгенерировать список всех возможных строк из символов s1 и посмотреть, входит ли в него s2. Но в данном подходе есть одна закавырка: при генерации всех возможных строк из s1 есть n возможных первых символов, \(n-1\) возможных вторых символов и так далее. Отсюда общее количество строк-кандидатов будет \(n*(n-1)*(n-2)*...*3*2*1\), что есть \(n!\). Несмотря на то, что некоторые строки будут дублироваться, программа об этом заранее знать не будет, поэтому всё равно сгенерирует \(n!\) различных строк.

Решение \(n!\) с увеличением n возрастает быстрее, чем даже \(2^{n}\). Фактически, при длине s1 в 20 символов мы получим \(20!=2,432,902,008,176,640,000\) возможных строк-кандидатов. Если мы будем обрабатывать одну вероятность каждую секунду, то на весь список уйдёт 77 146 816 596 лет. Похоже, это совсем не хорошее решение.

Решение 4: Подсчитывай и сравнивай¶

Наше последнее решения задачи про анаграммы воспользуется преимуществом того факта, что любые две анаграммы имеют одинаковое количество букв a, b и так далее. Для того, чтобы решить, являются ли строки анаграммами, мы сначала подсчитаем, сколько раз в них встречается каждый символ. Поскольку возможных букв 26, то мы можем использовать список из 26 счётчиков - по одному на каждый символ. Каждый раз, когда мы видим конкретную букву, мы увеличиваем соответствующий ей счётчик на единицу. В итоге, если оба списка счётчиков идентичны, то строки - анаграммы. Это решение показано в ActiveCode 6

Решение вновь имеет некоторое количество циклов. Однако, в отличии от первого варианта, ни один из них не является вложенным. Два первых цикла, используемые для подсчёта символов, базируются на n. Третий цикл - сравнение двух списков счётчиков - всегда состоит из 26 итераций (поскольку строки состоят из 26 возможных элементов). Складывая всё вместе, получим \(T(n)=2n+26\) шагов, что является \(O(n)\). Мы нашли алгоритм с линейным порядком величины для решения нашей задачи.

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

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

test = 0
for i in range(n):
   for j in range(n):
      test = test + i * j

test = 0
for i in range(n):
   test = test + 1

for j in range(n):
   test = test - 1

i = n
while i > 0:
   k = 2 + 2
   i = i // 2