Теоретическая и фактическая сложность времени для алгоритма расчета 2 ^ n

Question

Я пытаюсь вычислить сложность времени и сравнить ее с фактическим временем вычисления.

Если я не ошибаюсь, сложность по времени составляет O (log (n)), но с точки зрения фактического времени вычислений она больше похожа на O (n) или даже O (nlog (n)).

В чем может быть причина этой разницы?

def pow(n):
    """Return 2**n, where n is a nonnegative integer."""
    if n == 0:
        return 1
    x = pow(n//2)
    if n%2 == 0:
        return x*x
    return 2*x*x

Теоретическая сложность времени :

Фактическое время работы :

Answer 1

Я подозревал, что ваш расчет времени не точный, поэтому я сделал это, используя timeit, вот моя статистика:

import timeit
# N
sx = [10, 100, 1000, 10e4, 10e5, 5e5, 10e6, 2e6, 5e6]
# average runtime in seconds
sy = [timeit.timeit('pow(%d)' % i, number=100, globals=globals()) for i in sx]

---

Обновление:

Ну, код действительно работал с O (n * log (n)) ...! Возможное объяснение состоит в том, что умножение / деление не является O (1) для больших чисел, поэтому эта часть не выполняется:

T(n) = 1 + T(n//2)
     = 1 + 1 + T(n//4)
#      ^   ^
#     mul>1
#         div>1
# when n is large

---

Эксперимент с умножением и делением:

mul = lambda x: x*x
div = lambda y: x//2

s1 = [timeit.timeit('mul(%d)' % i, number=1000, globals=globals()) for i in sx]
s2 = [timeit.timeit('div(%d)' % i, number=1000, globals=globals()) for i in sx]

И графики, одинаковые для mul и div - они не являются O (1) (?). Маленькие целые числа кажутся более эффективными, но не имеют большой разницы для больших целых чисел. Я не знаю, что может быть причиной тогда. (хотя я должен держать ответ здесь, если это может помочь)

Answer 2

Число итераций будет log (n, 2), но каждая итерация должна выполнить умножение между двумя числами, которые в два раза больше, чем в предыдущей итерации.

Лучшие алгоритмы умножения чисел с переменной точностью выполняются в O (N * log (N) * log (log (N))) или O (N ^ log (3)) где N - количество цифр (битов или слов), необходимое для представления числа. Казалось бы, эти две сложности на практике дают время выполнения, которое больше, чем O (log (n)).

Количество цифр двух чисел на каждой итерации равно 2 ^ i. Таким образом, общее время будет суммой умножения (x * x) сложностей для чисел, проходящих через log (n) итераций

Чтобы вычислить временную сложность функции на основе алгоритма умножения Шёнхаге – Штрассена, нам нужно было бы добавить временную сложность каждой итерации, используя: O (N * log (N) * log (log (N))):

∑ 2^i * log(2^i) * log(log(2^i)) [i = 0...log(n)]

∑ 2^i * i * log(i) [i = 0...log(n)]

, что было бы довольно сложно, поэтому давайте рассмотрим более простой сценарий.

Если в умножениях переменной точности Python использовался самый наивный алгоритм O (N ^ 2), время наихудшего случая можно выразить как:

∑ (2^i)^2 [i = 0...log(n)]

∑ 4^i [i = 0...log(n)]    

(4^(log(n)+1)-1)/3    # because ∑K^i [i=0..n] = (K^(n+1)-1)/(K-1)

( 4*4^log(n) - 1 ) / 3

( 4*(2^log(n))^2 - 1 ) / 3    

(4*n^2-1)/3   # 2^log(n) = n

(4/3)*n^2-1/3

Это будет O (n ^ 2), что говорит о том, что время итерации log (n) самоопределяется в пользу профиля сложности умножения.

Мы получим тот же результат, если применить это рассуждение к алгоритму умножения Карацубы: O (N ^ log (3)):

∑ (2^i)^log(3)    [i=0..log(n)]

∑ (2^log(3))^i    [i=0..log(n)]

∑ 3^i             [i=0..log(n)]

( 3^(log(n)+1) - 1 ) / 2   # because ∑K^i [i=0..n] = (K^(n+1)-1)/(K-1)

( 3*3^log(n) - 1 ) / 2

( 3*(2^log(3))^log(n) - 1 ) / 2

( 3*(2^log(n))^log(3) - 1 ) / 2

(3/2)*n^log(3) - 1/2

, что соответствует O (n ^ log (3)) и подтверждает теорию.

Обратите внимание, что последний столбец вашей таблицы измерений вводит в заблуждение, поскольку вы прогрессируете n в геометрической прогрессии. Это меняет значение t [i] / t [i-1] и его интерпретацию для оценки сложности времени. Было бы более значимым, если бы прогрессия между N [i] и N [i-1] была линейной.
Принимая во внимание отношение N [i] / N [i-1] в расчете, я обнаружил, что результаты, похоже, больше коррелируют с O (n ^ log (3)), что позволяет предположить, что Python использует Карацубу для умножения больших целых чисел. , (для версии 3.7.1 в MacOS) Однако эта корреляция очень слабая.

ЗАКЛЮЧИТЕЛЬНЫЙ ОТВЕТ: O (log (N))

Проведя больше тестов, я понял, что существуют большие различия во времени, затрачиваемом на умножение больших чисел. Иногда большие числа занимают значительно меньше времени, чем меньшие. Это делает временные цифры подозрительными, и корреляция с временной сложностью, основанной на небольшой и нерегулярной выборке, не будет окончательной.
Для более крупной и более равномерно распределенной выборки время сильно коррелирует (0,99) с log (N) . Это будет означать, что различия, вносимые накладными расходами умножения, влияют только на фиксированные точки в диапазоне значений. Преднамеренный выбор значений N, которые находятся на несколько порядков друг от друга, усугубил влияние этих фиксированных точек, что исказило результаты.

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

Answer 3

Это потому, что умножьте 2 маленьких числа на O (1). Но умножьте 2 длинных числа (N - num) O (log (N) ** 2). https://en.wikipedia.org/wiki/Multiplication_algorithm Так что на каждом шаге время увеличивается не O (log (N))

Answer 4

Для некоторых целочисленных значений Python будет внутренне использовать «длинную репрезентацию». В вашем случае это происходит где-то после n=63, поэтому ваша теоретическая сложность времени должна быть правильной только для значений n < 63.

Для "длинного представления" умножение 2 чисел (x * y) имеет сложность больше, чем O(1):

• для x == y (например, x*x) сложность составляет вокруг O(Py_SIZE(x)² / 2).

• для x != y (например, 2*x) умножения выполняется как " Longbook умножение ", поэтому сложность будет O(Py_SIZE(x)*Py_SIZE(y)). В вашем случае это также может немного повлиять на производительность, потому что 2*x*x будет делать (2*x)*x, тогда как более быстрый способ будет 2*(x*x)

И поэтому при n> = 63 теоретическая сложность также должна учитывать сложность умножений.

Можно измерить «чистую» сложность пользовательского pow (игнорируя сложность умножения), если вы можете уменьшить сложность умножения до O(1). Например:

SQUARE_CACHE = {}
HALFS_CACHE = {}


def square_and_double(x, do_double=False):
    key = hash((x, do_double))
    if key not in SQUARE_CACHE:
        if do_double:
            SQUARE_CACHE[key] = 2 * square_and_double(x, False)
        else:
            SQUARE_CACHE[key] = x*x
    return SQUARE_CACHE[key]


def half_and_remainder(x):
    key = hash(x)
    if key not in HALFS_CACHE:
        HALFS_CACHE[key] = divmod(x, 2)
    return HALFS_CACHE[key]


def pow(n):
    """Return 2**n, where n is a non-negative integer."""
    if n == 0:
        return 1
    x = pow(n//2)
    return square_and_double(x, do_double=bool(n % 2 != 0))


def pow_alt(n):
    """Return 2**n, where n is a non-negative integer."""
    if n == 0:
        return 1
    half_n, remainder = half_and_remainder(n)
    x = pow_alt(half_n)
    return square_and_double(x, do_double=bool(remainder != 0))

import timeit
import math


# Values of n:
sx = sorted([int(x) for x in [100, 1000, 10e4, 10e5, 5e5, 10e6, 2e6, 5e6, 10e7, 10e8, 10e9]])

# Fill caches of `square_and_double` and `half_and_remainder` to ensure that complexity of both `x*x` and of `divmod(x, 2)` are O(1):
[pow_alt(n) for n in sx]

# Average runtime in ms:
sy = [timeit.timeit('pow_alt(%d)' % n, number=500, globals=globals())*1000 for n in sx]

# Theoretical values:
base = 2
sy_theory = [sy[0]]
t0 = sy[0] / (math.log(sx[0], base))
sy_theory.extend([
    t0*math.log(x, base)
    for x in sx[1:]
])
print("real timings:")
print(sy)
print("\ntheory timings:")
print(sy_theory)

print('\n\nt/t_prev:')
print("real:")
print(['--' if i == 0 else "%.2f" % (sy[i]/sy[i-1]) for i in range(len(sy))])
print("\ntheory:")
print(['--' if i == 0 else "%.2f" % (sy_theory[i]/sy_theory[i-1]) for i in range(len(sy_theory))])

# OUTPUT:
real timings:
[1.7171500003314577, 2.515988002414815, 4.5264500004122965, 4.929114998958539, 5.251838003459852, 5.606903003354091, 6.680275000690017, 6.948587004444562, 7.609975000377744, 8.97067000187235, 16.48820400441764]

theory timings:
[1.7171500003314577, 2.5757250004971866, 4.292875000828644, 4.892993172417281, 5.151450000994373, 5.409906829571465, 5.751568172583011, 6.010025001160103, 6.868600001325832, 7.727175001491561, 8.585750001657289]


t/t_prev:
real:
['--', '1.47', '1.80', '1.09', '1.07', '1.07', '1.19', '1.04', '1.10', '1.18', '1.84']

theory:
['--', '1.50', '1.67', '1.14', '1.05', '1.05', '1.06', '1.04', '1.14', '1.12', '1.11']

Результаты все еще не идеальны, но близки к теоретическим O(log(n))

Answer 5

Вы должны учитывать истинный размер ввода функции.Это не величина из n, а число битов, необходимых для представления n, которое логарифмическое по величине.То есть деление числа на 2 не сокращает входной размер пополам: оно только уменьшает его на 1 бит.Это означает, что для n -битного числа (значение которого находится в пределах от 2 ^ n до 2 ^ (n + 1)) время работы действительно логарифмически по величине, но линейное в количествебиты.

    n       lg n                 bits to represent n
    --------------------------------------
    10     between 2 and 3      4 (1010)
   100     between 4 and 5      7 (1100100)
  1000     just under  7       10 (1111101000)
 10000     between 9 and 10    14 (10011100010000)

Каждый раз, когда вы умножаете n на 10, вы увеличиваете входной размер только на 3-4 бита, примерно в 2 раза, а не в 10 раз.

Answer 6

Это может быть сложно, но есть разные случаи, которые вам придется исследовать для разных значений n, так как это рекурсивно.Это должно объяснить это https://en.wikipedia.org/wiki/Master_theorem_(analysis_of_algorithms).

Answer 7

Вы можете генерировать результаты, подобные учебникам, если посчитать, что они считают, предпринятые шаги:

def pow(n):
    global calls
    calls+=1
    """Return 2**n, where n is a nonnegative integer."""
    if n == 0:
        return 1
    x = pow(n//2)
    if n%2 == 0:
        return x*x
    return 2*x*x

def steppow(n):
    global calls
    calls=0
    pow(n)
    return calls

sx = [math.pow(10,n) for n in range(1,11)]
sy = [steppow(n)/math.log(n) for n in sx]
print(sy)

Тогда получится что-то вроде этого:

[2.1714724095162588, 1.737177927613007, 1.5924131003119235, 1.6286043071371943, 1.5634601348517065, 1.5200306866613815, 1.5510517210830421, 1.5200306866613813, 1.4959032154445342, 1.5200306866613813]

Там, где 1,52 ... кажется каким-то фаворитом.

Но фактическое время выполнения также включает в себя, казалось бы, невинные математические операции, которые также усложняются по мере того, как число физически увеличивается в памяти.CPython использует множество реализаций умножения, разветвляющихся в различных точках:

long_mul - это запись:

if (Py_ABS(Py_SIZE(a)) <= 1 && Py_ABS(Py_SIZE(b)) <= 1) {
    stwodigits v = (stwodigits)(MEDIUM_VALUE(a)) * MEDIUM_VALUE(b);
    return PyLong_FromLongLong((long long)v);
}

z = k_mul(a, b);

, если числа соответствуютв слове процессора они умножаются на месте (но результат может быть больше, следовательно, LongLong (*)), в противном случае они будут использовать k_mul(), что означает умножение Карацубы, которое также проверяетпара вещей, основанных на размере и значении:

i = a == b ? KARATSUBA_SQUARE_CUTOFF : KARATSUBA_CUTOFF;
if (asize <= i) {
    if (asize == 0)
        return (PyLongObject *)PyLong_FromLong(0);
    else
        return x_mul(a, b);
}

для более коротких чисел, используется классический алгоритм, x_mul(), и проверка на короткое замыкание также зависитна продукте, являющемся квадратом, beause x_mul() имеет оптимизированный путь кода для вычисления x*x -подобных выражений.Тем не менее, выше определенного размера в памяти, алгоритм остается локально, но затем он делает еще одну проверку того, насколько различны величины двух значений:

if (2 * asize <= bsize)
    return k_lopsided_mul(a, b);

, возможно, переход на еще один алгоритм,k_lopsided_mul(), который по-прежнему является Карацубой, но оптимизирован для умножения чисел со значительной разницей в величине.

Короче говоря, даже значение 2*x*x имеет значение, если заменить его на x*x*2, timeit результаты будут отличаться:

2*x*x: [0.00020009249478223623, 0.0002965123323532072, 0.00034258906889154733, 0.0024181753953639975, 0.03395215528201522, 0.4794894526936972, 4.802882867816082]
x*x*2: [0.00014974939375012042, 0.00020265231347948998, 0.00034002925019471775, 0.0024501731290706985, 0.03400164511014836, 0.462764023966729, 4.841786565730171]

(измеряется как

sx = [math.pow(10,n) for n in range(1,8)]
sy = [timeit.timeit('pow(%d)' % i, number=100, globals=globals()) for i in sx]

)

(*), кстати,поскольку размер результата часто переоценивают (как в самом начале, long*long может соответствовать или не соответствовать long впоследствии), есть также функция long_normalize, которая наend действительно тратит время на освобождение дополнительной памяти (см. комментарий выше), но все же устанавливает правильный размер для внутреннего объекта, что включает цикл, подсчитывающий нули перед фактическим числом.