Что представляет собой экспоненциальная сложность времени?

Question

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

Этот псевдокод работает за экспоненциальное время,O (2 ^ n):

Prime(n):
    for i in range(2, n-1)
        if n % i == 0
            return False
    return True

Этот псевдокод выполняется в два раза быстрее, чем в предыдущем примере, но я изо всех сил пытаюсь понять, является ли сложность времени все еще O (2 ^ n) или нет:

Prime(n):
    for i in range(2, (n/2+1))
        if n % i == 0
            return False
    return True

Answer 1

Экспоненциальный или линейный вопрос - это вопрос о том, как представлен вход и модель машины Если ввод представлен в одинарном формате (например, 7 отправлено как 1111111), и машина может выполнять постоянное деление времени по числам, тогда да, алгоритм является линейным временем. Однако двоичное представление n использует около lg n битов, а величина n имеет экспоненциальное отношение к lg n (n = 2 ^ (lg n)).

Учитывая, что число итераций цикла находится в пределах постоянного множителя для обоих решений, они находятся в одном большом классе O, Theta (n). Это экспоненциально, если вход имеет lg n битов, и линейно, если оно имеет n.

Answer 2

В качестве простой интуиции о том, что такое big-O (big-O) и big-Θ (big-Theta), они рассказывают о том, как изменяется количество операций, которые необходимо выполнить, когда вы значительно увеличите размерпроблема (например, в 2 раза).

Линейная сложность по времени означает, что вы увеличиваете размер в 2 раза, количество шагов, которые вам нужно выполнить, также увеличивается примерно в 2 раза.Это то, что называется Θ(n) и часто взаимозаменяемо, но не точно O(n) (разница между O и Θ заключается в том, что O обеспечивает только верхнюю границу, а Θ гарантирует как верхнюю, так и нижнюю границу).

Логарифмическая сложность по времени (Θ(log(N))) означает, что при увеличении размера в 2 раза количество шагов, которые вам нужно выполнить, увеличивается на некоторое фиксированное количество операций.Например, используя бинарный поиск, вы можете найти данный элемент в вдвое длинном списке, используя только одну итерацию цикла.

Аналогично, экспоненциальная сложность времени (Θ(a^N) для некоторой константы a > 1) означает, что если вы увеличитедля решения этой проблемы всего в 1 раз вам потребуется в * 1016 раз больше операций.(Обратите внимание, что между Θ(2^N) и 2^Θ(N) есть небольшая разница, и фактически второй является более общим, оба лежат в экспоненциальном времени, но ни один из двух не покрывает все это, см. wiki для некоторых другихдетали)

Обратите внимание, что эти определения в значительной степени зависят от того, как вы определяете "размер задачи"

. Как правильно заметил @DavidEisenstat, существует два возможных контекста, в которых ваш алгоритм может быть виден:

1. Некоторые числа фиксированной ширины (например, 32-разрядные числа).В таком контексте очевидной мерой сложности алгоритма первичного тестирования является само проверяемое значение.В таком случае ваш алгоритм является линейным.

2. На практике существует множество контекстов, в которых алгоритм простого тестирования должен работать для действительно больших чисел.Например, многие криптоалгоритмы, используемые сегодня (например, обмен ключами Диффи-Хеллмана или RSA ), используют очень большие простые числа, такие как 512-битные, 1024-битные и так далее.Также в этом контексте безопасность измеряется количеством этих битов, а не конкретным простым значением.Таким образом, в таких условиях естественным способом измерения размера задачи является количество бит.И теперь возникает вопрос: сколько операций нам нужно выполнить, чтобы проверить значение известного размера в битах, используя ваш алгоритм?Очевидно, что если значение N имеет m битов, оно равно N ≈ 2^m.Таким образом, ваш алгоритм из линейного Θ(N) преобразуется в экспоненциальный 2^Θ(m).Другими словами, чтобы решить проблему для значения, которое на 1 бит длиннее, вам нужно выполнить примерно в 2 раза больше работы.

Answer 3

Я надеюсь, что это объяснит вам, почему они на самом деле являются линейными.

Предположим, вы вызываете функцию и видите, сколько раз они выполнялись

Prime(n): # 1 time 
    for i in range(2, n-1) #n-1-1 times
        if n % i == 0  # 1 time 
            return False # 1 time

    return True # 1 time


# overall -> n

Prime(n): # Time
    for i in range(2, (n/2+1)) # n//(2+1) -1-1 time
        if n % i == 0 # 1 time
            return False # 1 time
    return True # 1 time

# overall -> n/2 times -> n times

Это показывает, что простое число является линейной функцией.

O (n ^ 2) может быть из-за блока кода, где вызывается эта функция.