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

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

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

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

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

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) может быть из-за блока кода, где эта функция называется.

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

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

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

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

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

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

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

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