Пытаясь выяснить время комплексов - PullRequest
Новая
       36

Пытаясь выяснить время комплексов

0 голосов
/ 12 июня 2018

Я пытаюсь выяснить временные сложности для следующего:

Первый: 

 j = 1
 while j < n:
    j += log(j + 5)

Это будет log n ?

Во-вторых, рекуррентное соотношение: 

 T(n) = T(n/2) + T(n/4) + n

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

Далее, еще одно рекуррентное соотношение: 

 T(n) = T(n/2) + log(n)

Я вполне уверен, что основная теорема может применяться здесь.Оставляя нас с: 

 a = 1, b = 2, f(n) = log(n)

Это означает, что мы будем сравнивать 

 n^(log_2(1)) to log(n) ==> n^0 to log(n)

Создание тета (log (n))

Наконец 

 j=1
 while(j<n):
    k=j
    while k<n:
       k += sqrt(k)
    j += 0.25*j

Могу сказать, что внешний цикл будет работать 4 раза.Мне неясно, что касается внутреннего цикла, однако.Будет ли это log ^ 2 n log log n или я совершенно не в себе.

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

1 Ответ

0 голосов
/ 12 июня 2018

Первое значение равно O(n), как мы знаем каждый раз, когда по крайней мере 1 добавляется к предыдущему результату.

Если вы расширяете рекуррентное уравнение, второе значение равно: 

T(n) = 2T(n/4) + T(n/8) + n + n/2 < 3T(n/4) + 3n/2

Из основной теоремы мы можем сказать, что T(n) = \Theta(n).

Третье верно и \Theta(log(n)).Внешний цикл в четвертом цикле равен T(n+1) = 5T(n)/4.Это означает, что внешний цикл запускается log_{1.25}n.В худшем случае можно сказать, что внутренний цикл работает в O(n).Следовательно, это будет O(nlog(n)).Если вы хотите более сложный анализ сложности, вам нужно больше изучить,

...