Вопрос, связанный с суммированием и Θ-обозначением времени работы

Я думаю, что понимаю концепцию суммирования и Θ-обозначения, однако я не очень понимаю вопрос ниже.

Если я правильно понял, я должен выписать суммы (функции слева), затем сравнить их порядок роста с функциями справа (поправьте меня, если я ошибаюсь).

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

На самом деле слева больше функций, но я удалил их, чтобы вопрос не выглядел запутанным.

введите описание изображения здесь

Ответы (1)

Несколько странно, что ваше слагаемое не включает никаких я , так как вы суммируете из я "=" 1 вплоть до н . Предполагая, что вы не ошиблись,

я ( н ) "=" ∑ я "=" 1 н ( 4 + бревно ⁡ н ) "=" н ( бревно ⁡ н + 4 )

У вас есть н бревно ⁡ н срок и 4 н срок. Если вы понимаете Θ -notation хорошо, вы должны быть в состоянии ответить на это. Для других вопросов вам следует расширить сумму, если она есть, и посмотреть, сможете ли вы переписать ее без суммы для связанного анализа.

Спасибо, так что в основном все, что мне нужно сделать, это расширить суммирование, а затем взять член с наивысшим порядком, который будет соответствующей функцией Θ-обозначения? Итак, n(logn+4) будет Θ(n)?
Нет, н бревно ⁡ н > н так что это Θ ( н бревно ⁡ н ) .
Вопрос, связанный с суммированием и Θ-обозначением времени работы
СпросиСетьПолитика конфиденциальности1y, 0v