#algorithm #recurrence #master-theorem
#алгоритм #повторение #мастер-теорема
Вопрос:
Итак, у меня есть
T(n) = 2T(n/2) n^2
И я нашел a = 2, b = 2 и f(n) = n^2, и чтобы получить n^2, я использовал случай 3 для основной теоремы, которая является
f(n) = большая Омега ( n ^ logba E )
и я нашел большую Омегу (n^2)
Итак, как я могу решить
большая тета ( большая Омега (n^2) ) ?
Кроме того, верны ли мои расчеты?
Комментарии:
1. да, вы правы.
2. вы не можете решить
big theta ( big Omega (n^2) ), так как омега и тета описывают границы и не являются реальными конкретными функциями, следовательно, вы что-то не так поняли, перейдя к терминуbig theta ( big Omega (n^2) )3. @DuDa В формуле, которая у меня есть, написано » большая тета ( f(n))», и я получил «f(n) = большая омега (n^2)». Я использую неправильную формулу? или ответ уже «большая омега (n^2)»
4.
f(n) = big theta ( g(n) )это общее написаниеf(n) ∈ big theta ( g(n) ). Поэтому вы не можете заниматься арифметикой, к которой привыкли. Я не так хорошо знаком с основной теоремой, я посмотрю на нее.5. Итак, что касается википедии, то вывод таков
T(n): она находится внутриBig Theta (f(n)). Это означает, что ваша временная сложность имеет верхнюю границу чего — то подобногоf(n)и нижнюю границу чего-то подобногоf(n). Таким образом, ваша временная сложность квадратна в худшем и лучшем случае (f(n)=n^2). Вы не можете вычислить конкретные значения с помощью основной теоремы, «просто» границы.