Сложность алгоритма с входом размера фиксации
Я нашел некоторые ссылки о большой нотации O, но насколько я могу понять, что сложность алгоритма является функцией размера входных данных.
Например, если сложность пузырьковой сортировки O(n^2), n размер входного массива.Правильно?
Но, как может я определенная сложность алгоритма, который зафиксировал входной размер и зависит значений входа. Например, нахождение Наибольшего общего делителя (GCD) было бы похоже на это:
def GCD(x, y):
while x != y:
if x < y:
x, y = y - x, x
else:
x, y = x - y, x
return x
Что такое сложность этого алгоритма? И как это определяется?
Править: Изменившее имя функции и исправленное название алгоритма. ShreevatsaR, благодарит указать на это.
4 ответа
Люди играют немного быстро и свободно с нотацией Big-O. В случае GCD они обычно делают это в 2 способах:
1) Вы правы, алгоритмическая сложность и, следовательно, нотация Big-O, должны быть указаны с точки зрения размера в битах из ввода, не с точки зрения значений ввода. Вот как P, NP и так далее определены. Предполагая, что двоичные входные и произвольно большое количество (например, представление Bignum), и N Количество битов ввода, ваш GCD требует не более 2 ^ n вычитаний, каждый из которых требует времени O (n) для проведения каждой цифры Числа вычитаются. Так что это o (n * 2 ^ n). Конечно, GCD может быть намного быстрее, если вы используете разделение, а не вычитание: O (n ^ 2).
Итак, когда мы говорим, что тестирование просьбы было доказано в 2002 году для выполнения в полиноме , это техническое определение сложности, и мы имеем в виду многочлены в количестве цифр (что является сложной частью ), не полиномиальный в самом входном номере сам (который тривиально легко сделать в «подлинейном времени» с использованием пробной дивизии).
Но на практике, для алгоритмов, которые предпринимают фиксированное количество целочисленных входов, более удобно говорить о сложности, как будто N был входным, а не размером ввода. Это не вредно, если вы ясно, что вы имеете в виду в случаях, которые могут быть неоднозначными.
2) На практике целочисленные входы часто часто являются фиксированными, 32 битами или что-то еще, а операции на них, такие как добавление, умножение и деление O (1) время. Мы используем эти факты избирательно в нашем анализе заказов. Технически, если ваша программа GCD принимает только входы до (2 ^ 32-1), то это o (1). У него есть фиксированная верхняя сторона его время работы. Конец анализа.
Хотя технически правильно это не очень полезный анализ. Почти все, что вы делаете на реальном компьютере, это O (1) на той же основе, что размер проблемы ограничен оборудованием.
Обычно удобнее принять, что добавление составляет O (1), поскольку числа являются фиксированными размерами, но игнорируют, что GCD также является O (1), притворяется, что его поведение в диапазоне [1, 2 ^ 32) продлевает до бесконечности и проанализировать его на этой основе. Затем с N Max от двух входов он выходит O (n): o (n) вычитания, каждый из которых принимает постоянное время.
Опять же, это не двусмысленно, как только вы узнаете, каковы условия использования, но остерегайтесь неправильно сравнения первого анализа, который я дал алгоритму Евклида с делением, O (N ^ 2), против этого анализа алгоритма с вычитанием , НА). N не то же самое в каждом, а вычитание не быстрее; -)
входной размер - это сумма размеров чисел x и y (например, сколько цифр в номере)
Большая O сложность - это наихудший случай асимптотического поведения во время выполнения. Оно не обязательно зависит от размера входного сигнала (количества входов) конкретного алгоритма - хотя так часто бывает. Другими словами, именно лимитирующая функция описывает время выполнения, так как входы берутся на бесконечность.
В вашем случае, если x или y неограничены, то и асимптотическое время выполнения тоже. Если нет, подумайте о времени выполнения, если x = 1, а y = Int32.Max?
.Обозначение Big-O должно указать, что измеряется.
Например, нотация Big-O для алгоритмов сортировки обычно измеряет количество сравнений.
Ваш пример GCD может быть измерен по сравнению со значениями x и y против количества выполненных инструкций. Давайте посмотрим больше внимательно:
def GCD(x, y):
while x != y: # 1
if x < y: # 2
x, y = y - x, x # 3
else: # 4
x, y = x - y, x # 5
return x # 6
работать изнутри наружу.
Неважно, что значения x и y , шаги 3 и 5 всегда будут принимать одну инструкцию. Следовательно, , если отчет о шаге 2 всегда будет принимать два инструкции.
Чем сложный вопрос - это шаг 1. С каждой итерацией либо x , либо y будет понижен меньшим значением. Предположим, что X> Y . Одно из двух вещей произойдет:
, если он начал, что
x% y == 0, то цикл будет выполнен(x / y) - 1раз и программа остановится.В противном случае
xx будет уменьшен(X / Y)раз, прежде чем он меньше чем меньшеy, и программа будет продолжаться.
Вы можете легко измерить количество инструкций для любого данного x и y . Вы можете легко показать, что для данного номера Z , вам никогда не понадобится более Z - 1 вычитание - или 2 * (Z-1) инструкции. (Подумайте о GCD (Z, 1) .)