Большинство программистов имеют, по крайней мере, проходящее знакомство с обозначениями Big-O. Это метод, который используется для поиска верхней границы при выполнении времени и пространства алгоритмов, поскольку вход становится больше.
Давайте возьмем сортировку списка в качестве типичного примера: разные алгоритмы будут иметь различное поведение, поскольку количество элементов для сортировки увеличивается. Очень простой алгоритм может перевернуть список в поисках самого маленького элемента, который он приносит в переднюю часть списка. Затем он повторяет тот же процесс для оставшейся части списка. В этом случае мы сначала проходим список размеров N, чтобы найти наименьший элемент, затем список размеров N-1, N-2 и т. Д. Это означает, что мы должны выполнять сравнения n × (n+1)/2. Поэтому такой алгоритм находится в O (n 2 ), или Полином (квадратично быть более точным), относительно количества необходимых сравнений. В большой схеме вещей это считается не так уж плохо. Тем не менее, существуют лучшие алгоритмы, которые могут сортировать элементы во время O (n × log n).
Вообще говоря, сложность проблем может быть разбита на 3 больших категории:
Если они находятся в O (1), O (log n), O (SQRT N), O (n) или O (N × log n), алгоритмы обычно считаются справедливо Трафта , это причудливый способ сказать, что они Управляемый .
Алгоритмы, которые находятся в полиномиальной сложности, по крайней мере, степень 2, например, O (n 2 ), O (n 3 ) и т. Д., Дорожаются более дорогие для решения, поскольку вход становится все больше. Эта степень сложности не идеальна, но она часто по-прежнему в порядке для многих видов реальных проблем, если показатель маленький.
O (2 N ) Алгоритмы требуют экспоненциальный Ресурсы. Это означает, что мы должны продолжать удвоить ресурсы для небольшого увеличения размера входа. Алгоритмы, которые являются экспоненциальными или хуже (например, факториал), как правило, считаются неразрешимый Анкет Прыжок в вычислительных требованиях происходит очень быстро, поэтому могут быть решены только небольшие экземпляры таких проблем, даже с большим количеством вычислительной мощности.
Иногда люди говорят, что Big-O-это мера худший случай спектакль. В терминологии есть некоторые нюансы. Биг-о измеряет верхняя граница по производительности по сравнению с входом. Тем не менее, алгоритм может иметь другой большой-O для различных видов ввода. Обычно Лучший случай , Худший случай и Средний случай считаются. Например, QuickSort Известно, что имеет худший случай O (n 2 ), но обычно это O (n × log n).
В этой статье я хотел бы исследовать что-то, что может быть сложным, а именно, что Big-O измеряется по отношению к Длина ввода Анкет Это означает, что Big-O может быть отличным для одного и того же алгоритма, в зависимости от того, как мы представляем вход! Это может показаться запутанным, поэтому давайте посмотрим на конкретный пример.
Факторинг целых чисел
Факторинг целых чисел для простых чисел – классическая проблема в области компьютерных наук. Некоторые широко используемые криптографические алгоритмы, такие как RSA, полагаются на то, что это сложная проблема, чтобы решить, когда числа становятся больше. Классический Алгоритмы для учета целых чисел требуют экспоненциального времени в худшем случае.
Факторизация не является NP, хотя. Если квантовые компьютеры с тысячами QBIT становятся реальностью, алгоритм Шора может использоваться для фактора целых чисел в полиномиальное время. Тем не менее, кажется, существует общий консенсус, что даже квантовые компьютеры не будут делать проблемы с полным NP.
Давайте рассмотрим наиболее интуитивно понятный и простой алгоритм для получения основных факторов числа. Предположим, у нас есть целое число, скажем, 124. Как мы можем включить это в простые числа? Мы можем начать с проверки, можно ли разделить число на 2:
124/
Результат ровный, так что давайте снова разделим на 2:
62/
Отсюда мы можем попробовать делиться на 3, 4, 5 и т. Д… до 30 лет, но все эти делители оставят остаток. Это означает, что 31 также является ярким. Он может быть разделен только равномерно сам по себе или на 1. Следовательно, основные факторы 124 составляют 2 × 2 × 31.
Только проверки факторов до квадратного корня
Мы можем сделать значительную оптимизацию в этом алгоритме: вместо того, чтобы проверять все возможные факторы до нашего числа N, нам нужно только проверить числа, которые меньше или равны квадратному корню N: Допустим, SQRT. По определению, S ×. Скажем, у нас есть целое число t, которое больше, чем S, но меньше N, и T является фактором N. Это означает N/, где U также является фактором. Поскольку t больше, чем S, вы должны быть меньше, чем S (в противном случае t x u будет больше, чем n). Поскольку u меньше S, мы бы попробовали его как фактор, прежде чем достичь S. Коэффициент n/u – T. Поэтому мы уже сталкивались с T, прежде чем добраться до S.
Чтобы найти все основные факторы n, это означает, что все, что нам нужно сделать, это попробовать все возможные факторы от 2 до квадратного корня N включительно. Ниже приведена простая реализация этого алгоритма в Python:
def prime_factors(n):
results = []
factor = 2
while factor * factor <= n:
(n, intermediate_results) = check_factor(n, factor)
results += intermediate_results
factor += 1
if (n > 1):
results += [n]
return results
def check_factor(n, factor):
results = []
(q, r) = divmod(n, factor)
while r == 0:
results.append(factor)
n = q
(q, r) = divmod(n, factor)
return n, results
Мы можем дополнительно сократить время выполнения этого алгоритма вдвое, пропустив равномерные числа, превышающие 2, поскольку любые четные факторы будут извлечены путем проверки на разделение на 2. Хотя это может быть значительным на практике, это не изменит сложность с точки зрения Big-O. Big-O, как правило, является крупнозернистым инструментом, который ищет всеобъемлющую модель роста. Постоянные факторы и условия более низкого порядка, как правило, игнорируются.
Худший случай
Когда мы учитываем число n, сколько подразделений нам нужно выполнять как n увеличение? Худший случай для нашего алгоритма – это то, когда n является ярким: наш алгоритм должен будет попробовать (безуспешно) все числа от 2 до квадратного корня N. Поэтому наш алгоритм находится в O (SQRT N) для худшего случая. Допустим, мы пытаемся учитывать основное число 1000003. Нам нужно будет проверить каждое из чисел от 2 до 1000, поэтому мы выполним (SQRT N) – 1 подразделения.
Длина ввода против величины
На первый взгляд, этот алгоритм кажется сублинейным. Тем не менее, есть ключевая проблема, которую легко пропустить. Количество битов, необходимых для кодирования n, является журналом 2 Северный Это означает, что количество подразделений составляет экспоненциальный по сравнению с длиной ввода в битах , хотя это сублинернее, когда мы сравниваем количество подразделений с n как величина. Если бы наш алгоритм был в O (n), то это было бы в O (2 b ) где b – количество битов в Н. Однако здесь это в O (SQRT N). Поскольку SQRT N требует половины количества битов в N, наш алгоритм оказывается в O (2 b/2 ).
На приведенном ниже графике показано количество подразделений по сравнению с количеством битов в n для наихудшего сценария:
Вместо использования десятичного или двоичного представления мы мог Кодируйте наше число, используя Unary Prevation, при котором ,,, и т. Д. В этом случае наш алгоритм действительно будет в O (SQRT N). Тем не менее, мы будем использовать гораздо больше, экспоненциально больше Память для хранения наших чисел, чем необходимо. В двоичном языке 1000003 требует всего 20 бит (11110100001001000011). В Unary для этого требуется миллион и 3 цифр! В десятичном виде 1000003 требует 7 цифр, что даже меньше, чем 20 цифр в двоичном. Тем не менее, оба пропорциональны журналу числа, поэтому такая разница обычно не очень важна для Big-O. Например, чтобы преобразовать журнал в базе 2 в базу 10, мы используем журнал уравнения 10 2 N/log 2 10 ≈ 1/3,32 × log 2 N. Они прямо пропорциональны друг другу.
По мере того, как мы увеличиваем количество битов в N, нам нужно экспоненциально больше подразделений, чтобы получить основные факторы числа. Конечно, число N также значительно увеличивается по мере увеличения количества битов. Вот почему этот тип алгоритма иногда называют Псевдо-полиномиал Анкет Чтобы увидеть влияние экспоненциального количества необходимых подразделений, мы должны продолжать увеличивать количество битов, работая с по -настоящему огромным числом. Ключевым моментом, о которой я думаю, является то, что число N является фактическим вводом, в отличие от, скажем, списка с n элементами в нем.
Алгоритм псевдополиномиального времени будет отображать «экспоненциальное поведение» только при столкновении с экземплярами, содержащими «экспоненциально большие» числа, которые могут быть редкими для приложений, которые нас интересуют. Если это так, этот тип алгоритма может служить нашим целям почти так же, как алгоритм полиномиального времени. — Компьютеры и неразрешимость В Майкл Р. Гари и Дэвид С. Джонсон
Типичный случай
Я не знаю, как определить Big-O для анализа типичного или среднего случая, но я попытался сделать несколько симуляций, чтобы получить приблизительную идею. Мы видим, что кривая все еще выглядит экспоненциальной.
Это явно намного лучше, чем худший случай, хотя. Ниже приведен график наихудшего случая по сравнению с этой приблизительной оценкой типичного случая. Я сгенерировал случайные числа в диапазоне 2 B-1 <2 b Где количество битов, B, составило с 3 до 48. Для каждой длины бита я факторировал 10 000 случайно сгенерированных чисел. Мы видим, что количество подразделений намного меньше для случайных чисел по сравнению с простыми числами:
Я думаю, что причина в том, что, поскольку мы увеличиваем количество бит в наших числах, процент факторов кандидатов, которые нам необходимы для проверки тенденций вниз. Это, конечно, намного меньше, чем SQRT N. Интуитивно это имеет смысл для меня, так как мы ожидаем, что случайные числа в данном диапазоне будут иметь гораздо больше небольших основных факторов, чем крупные.
Эти результаты на самом деле очень близки к тому, что мы ожидаем, если бы мы использовали пробное разделение с Указанный список основных факторов Анкет В этом случае вместо O (2 b/2 ), мы имеем O (2 b/2 /b × 2/ln 2). Это говорит о том, что, когда мы выбираем числа случайным образом, большую часть времени мы делаем на самом деле, просто нужно проверить список относительно небольших простых чисел.
Кроме того, каждый раз, когда мы находим основной фактор, мы уменьшаем диапазон факторов, которые следует учитывать по квадратному корню предыдущего коэффициента. Во многих случаях это может очень быстро сократить количество подразделений.
Ниже приведено соотношение факторов, которые фактически проверяются по сравнению с SQRT N. Для 3-битных чисел, то есть 100 (4), 101 (5), 110 (6) и 111 (7), есть только один фактор для проверки, 2. Поскольку мы всегда проверяем этот единственный фактор, соотношение составляет 1 или 100%. По мере того, как мы добираемся до больших и больших чисел, доля факторов -кандидатов, которые мы должны проверить, резко снижается, и тенденции к нулю, поскольку количество битов идет в бесконечность:
Лучший случай
В сценарии лучшего случая вход – это сила 2, поэтому все, что нужно, – это продолжать делиться на 2. С точки зрения числа n, это означает, что нам нужно только сделать журнал 2 N дивизии. Наш алгоритм будет находиться в O (log n) относительно величины n и в O (b) по количеству битов, B, в N., в то время как наихудший сценарий является экспоненциальным, лучший случай – это сценарий линейный.
Разделение не является постоянным
Я создал эту статью с точки зрения количества подразделений, необходимых для получения основных факторов числа, как если бы каждое разделение требует только постоянной работы. При работе с числами, которые можно разделить непосредственно с помощью машинной инструкции, это разумное предположение. Например, если у компьютера есть 64-битный Разделение Инструкция, не имеет значения, какие два 64-битных числа мы разделяем.
Однако для очень большого количества это разрушается. Если мы разделим два (огромные) числа, используя простой метод, такой как длинное разделение, это становится операцией O (B 2 ), где B – количество битов в числах. Я считаю, что использование более продвинутых методов, это можно улучшить, но оно останется хуже, чем O (B × log B). Однако, поскольку наш алгоритм основной факторизации является экспоненциальным, этот дополнительный фактор, вероятно, слишком мал, чтобы резко изменить картину. Экспоненциальный термин будет иметь тенденцию доминировать в любом дополнительном полиномиальном факторе.
Вывод
Несмотря на то, что существуют лучшие алгоритмы для получения основных факторов очень большого количества, оказывается, что все они по -прежнему являются в основном экспоненциальными в общем случае. Без квантовых компьютеров нет никакого известного способа эффективной факторизации чисел. Криптография RSA использует эту идею: RSA генерирует два очень больших первичных числа (каждое из тысяч битов ), а затем умножает их вместе. Он опирается на непрерывность поиска двух основных факторов этого огромного полученного продукта.
Когда люди знакомятся с Big-O, может быть легко пропустить тонкие моменты о том, как ввод кодируется. Я надеюсь, что эта статья может быть полезна в этом отношении.
Алгоритм динамического программирования для Рюкзак проблема является еще одним примером алгоритма псевдополиномиального времени.
Введение в Big-O
Если вы еще не сталкивались с идеей Big-O, вот две популярные статьи, которые вводят концепции Big-O и сложности:
- Кофе-разрыв Введение в сложность времени алгоритмов
- Биг-о нотация: Руководство для начинающих
Рекомендации
Оригинал: “https://dev.to/nestedsoftware/big-o-prime-factors-and-pseudo-polynomial-time-55cp”