Вычислительная сложность алгоритма c#

112

08 августа 2019, 03:10

Действия Action1 и Action2 выполняются за константное время. Определить вычислительную сложность алгоритма при A=1.5, A=1 и A=2.

Правильно ли я понимаю:

т.е при A=1.5, A=1 и A=2 сложность линейная, а при А >=3 цикл бесконечный?!

Answer 1

Запишем в виде, подходящем для Master Theorem

 T(n) = a * (n / b) + n^c
 T(n) = 2 * T(A/3 * n) + n
 т.е.  a = 2, b = 3/A,  c = 1

и оценим logb(a) для значений A =1, 1.5, 2

 A      b     logb(2)
 1      3      < 1
 3/2    2       1
 2      3/2     >1

В первом случае срабатывает третий вариант, и сложность Theta(n)

Во втором случае срабатывает второй вариант, и сложность Theta(n * log(n))

В третьем случае срабатывает первый вариант, и сложность
Theta(n^log3/2(2))~ Theta(n^1.7)

ТОП-10

Проблема заключается в корректности составления массива категорий и под категорийСобственно сам код:

104

Пытаюсь реализовать отправку уведомления о прочтении писем получателемВ интернете насерфил такие хейдеры:

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

103

Есть следующая форма:

144