Нахождение временной сложности O (n) - PullRequest
Новая
       9

Нахождение временной сложности O (n)

0 голосов
/ 24 апреля 2019

Рассмотрим этот код: 

import matplotlib.pyplot as plt

# Returns 2^n
def pow(n):

    if n == 0:
        return 1
    x = pow(n//2)
    if n%2 == 0:
        return x*x
    return 2*x*x

y = [10^4, 10^5,10^6, 10^7, 10^8, 10^9, 10^10]
z = []

for n in y:

    start = time.time()
    pow(n)
    print(n, time.time() - start) # elapsed time
    z.append(time.time()-start)

plt.plot(y,z)
plt.show()

Я пытаюсь выяснить, какова временная сложность рекурсивной функции pow(n).

Я вычислил сложность времени как O(log(n)), нопри использовании функции time.time() функция выглядит линейной.Почему?

Почему сложность времени O(n), а не O(log(n))?

Graph

1 Ответ

1 голос
/ 24 апреля 2019

Если вы замените все появления x*x в вашем примере на константу (например, 1) или умножение на сложение, вы увидите, что вы действительно получаете O(log(n)) сложность, так как ваша функция вызывается log(n) раз(хотя мы измеряем очень малое время в этом случае, поэтому результаты использования time могут не отражать сложность функции в этом случае).Я думаю, что вывод состоит в том, что ваше предположение о том, что умножение равно O(1), неверно (см., Например, этот вопрос ), в частности, поскольку умножаемые числа действительно велики и больше не вписываются в традиционные 32./ 64-битное представление.

...