Сложность алгоритма с вводом фиксированного размера

Question

Я нашел несколько ссылок на нотацию больших О, но насколько я понимаю, сложность алгоритма зависит от размера входных данных.

Например, если сложность сортировки пузырьков равна O(n^2), n - это размер входного массива. Правильно?

Но как я могу определить сложность алгоритма, который имеет фиксированный размер ввода и зависит от значений ввода. Например, поиск Greatest Common Divisor (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, спасибо, что указал на это.

Answer 1

Люди играют немного быстро и свободно с нотацией Big-O. В случае с GCD они обычно делают это двумя способами:

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 макс. Двумя входами получается O (N): O (N) вычитаний, каждый из которых занимает постоянное время.

Опять же, это не является двусмысленным, когда вы знаете, что такое круг ведения, но остерегайтесь неверного сравнения первого анализа, который я дал, алгоритма Евклида с делением O (N ^ 2), с этим анализом алгоритма с вычитанием O (N). N не одинаков в каждом, и вычитание не быстрее; -)

Answer 2

Обозначение 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 всегда будут занимать одну инструкцию. Следовательно, оператор if шага 2 всегда будет содержать две инструкции.

Более сложный вопрос - шаг 1. На каждой итерации x или y будет уменьшаться на меньшее значение. Предположим, что x > y. Произойдет одно из двух:

• Если он начал это x % y == 0, то цикл будет выполнен (x / y) - 1 раз и программа остановится.

• В противном случае x будет уменьшено * в 1031 * раз, прежде чем оно станет меньше y, и программа продолжит работу.

Вы можете легко измерить количество инструкций для любых заданных x и y. Вы можете легко показать, что для данного числа z вам никогда не понадобится больше, чем z - 1 вычитаний - или 2 * (z-1) инструкций. (Подумайте о gcd(z, 1).)

Answer 3

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

В вашем случае, если x или y не ограничены, то же относится и к асимптотическому времени выполнения. Если нет, подумайте о времени выполнения, если x = 1 и y = Int32.Max?

Answer 4

входной размер представляет собой сумму размеров чисел x и y (например, сколько цифр в числе)