Хобрук: Ваш путь к мастерству в программировании

Анализ времени выполнения Big Theta

Я не очень понимаю два вопроса ниже о 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" представляет журнал n в тета...

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

math big-o discrete-mathematics
06.10.2018

Ответы:


1

Во-первых, это Θ(log n).
Интуитивно понятно, что при умножении n на постоянный коэффициент T(n) увеличивается на постоянную величину.
Пример: T(n) = log(n)/log(3/2)

Второй – Θ(n).
Интуитивно понятно, что при умножении n на постоянный коэффициент T(n) увеличивается на величину, пропорциональную n.
Пример: T(n) = 2н

08.10.2018
  • Я только что разговаривал со своим профессором, и они сказали, что первое = правда, а второе = ложь. 08.10.2018
  • @JigarPatel: Вы имеете в виду, что правильный ответ на второй из двух тестовых вопросов, которые вы цитируете, ЛОЖЬ (что верно), или что вторая часть моего ответа ложь (что неверно) ? В такие моменты нам надлежит говорить точно. 08.10.2018
    • Новые материалы
    Управление состоянием в микрофронтендах
    Стратегии бесперебойного сотрудничества Микро-фронтенды — это быстро растущая тенденция в сфере фронтенда, гарантирующая, что удовольствие не ограничивается исключительно бэкэнд-системами..
    Декларативное и функциональное программирование в стиле LINQ с использованием JavaScript с использованием каррирования и генератора ...
    LINQ - одна из лучших функций C #, которая обеспечивает элегантный способ написания кода декларативного и функционального стиля, который легко читать и понимать. Благодаря таким функциям ES6,..
    Структуры данных в C ++ - Часть 1
    Реализация общих структур данных в C ++ C ++ - это расширение языка программирования C, которое поддерживает создание классов, поэтому оно известно как C с классами . Он используется для..
    Как я опубликовал свое первое приложение в App Store в 13 лет
    Как все началось Все началось три года назад летом после моего четвертого класса в начальной школе. Для меня, четвертого класса, лето кажется бесконечным, пока оно не закончится, и мой отец..
    Что в лицо
    Очерк о возвращении физиогномики и о том, почему мы должны это приветствовать. История начинается со странной науки. Р. Тора Бьорнсдоттир, Николас О. Рул. Видимость социального класса по..
    Почему шаблоны проектирования и почему нет?
    Сложность — мать всех проблем в программировании. Программное обеспечение должно быть разработано с точки зрения того, кто его поддерживает, а не того, кто его пишет, потому что программное..
    Создание дизайна обуви с помощью машинного обучения
    Обувь. Что подождать? Я думал, что речь пойдет о машинном обучении! Ну это так. Если бы вы пошли на Amazon, сколько обуви вы бы нашли? Наверное, много, не так ли? Но много ли в них..