Анализ времени выполнения Big Theta
Я действительно не понимаю 2 вопроса о T (n) ниже. Я понимаю, что означает тета, но не уверен в ответе на вопросы. Кто-нибудь может объяснить?
Я думал, что первый был ложным, потому что T (2n / 3) + 1 = Theta (log n), потому что добавленная константа 1 не имеет значения и log ближе к непрерывному уменьшению вдвое, но 2n / 3 не
Я думал, что второй верен, потому что T (n / 2) + n = Theta (n * log n), потому что линейное "n *" в Theta представляет "+ n" в T (n / 2) + n "n / 2" представляет собой log n в Theta ...
Ответы 1
Первый - Θ (log n).
Интуитивно понятно, что когда вы умножаете n на постоянный коэффициент, T (n) увеличивается на постоянную величину.
Пример: T (n) = log (n) / log (3/2)
Второй - Θ (n).
Интуитивно понятно, что когда вы умножаете n на постоянный коэффициент, T (n) увеличивается на величину, пропорциональную n.
Пример: T (n) = 2n
@JigarPatel: Вы имеете в виду, что правильный ответ на второй из двух приведенных вами тестовых вопросов - «ЛОЖЬ» (что верно), или что вторая часть моего ответа - ложный (что неверно)? В такие моменты нам следует говорить точно.
Я только что поговорил со своим профессором, и они сказали, что первый = правда, а второй = ложь.