subMethod (m) имеет сложность O (m), какова сложность следующего кода в худшем случае? - PullRequest
Новая
       3

subMethod (m) имеет сложность O (m), какова сложность следующего кода в худшем случае?

0 голосов
/ 10 марта 2020 
def func(n):
    j=1
    for i in range(n//2, n+1):
        while (j <= n):
            j = j * 2
            subMethod(i)
        if i > 100:
            while (j > 1):
            j = j - 1
            #doing something O(1)

i = 1, выход = 2 i = от 2 до 3, выход = 2,4 я = 4 до 7, выход = 2,4,8 я = 8 до 15, выход = 2,4,8,16 я = 16 до 31 выход = 2,4,8,16,32

1 Ответ

2 голосов
/ 10 марта 2020

Сначала l oop - это O (n), потому что это O (n / 2), и мы отбрасываем константы и члены более низкого порядка.

Второй l oop - это O (lg-n), потому что j равно 2 ^ k (то есть 2, 4, 8, 16, 32).

Третий l oop - это то, что есть j и отсчитывает, поэтому O (j). J начинается с 1 и обратите внимание, что он растет от 2 ^ k до n худшего случая. Скажем, n равно 1000. Когда j равно 500, следующая итерация будет 500 * 2 = 1000.

Сложность по времени составляет O (n + lg-n + lg-n + j) = O (n + 2lg -n + j) -> O (n + lgn + j) -> O (n) .

Мы опускаем lg-n, потому что скорость роста n при приближении n к бесконечности всегда будет опережать lg-n. Это так же, как когда мы отбрасываем n ^ 2, когда у нас есть n ^ 3, потому что последний растет со временем быстрее.

Мы опускаем j, потому что - может ли скорость роста j когда-либо опережать n, когда она зависит от n?

...