Введение в CS | 22.8: «Big Theta»: Оценка с обеих сторон, оставляем только доминирующий член

Полный курс — бесплатные упражнения, конспекты и обратная связь от ИИ: https://ludium.ai/courses/intro-cs-py... Большая О-ограничивает функцию сверху и ничего не говорит о противоположной стороне. Тета-ограничение замыкает её: одна функция g, масштабированная вверх, чтобы оставаться выше нашей, и масштабированная вниз, чтобы оставаться ниже неё. Именно это второе требование делает тета-ограничение точным, и именно поэтому функция имеет ровно одно тета-ограничение — член, который растёт быстрее всего. Работал над 3x² - 20x - 1 с ограничениями 4x² и 2x², а затем превратил в трёхэтапный рецепт для любой формулы стоимости: найти самый быстрорастущий член, отбросить его константу, отбросить всё остальное. Далее следуют девять практических формул, включая одну с двумя входными данными, и подсказка о том, какой буквой следует записать ответ. Ключевые понятия: Определение тета: верхняя и нижняя границы с использованием одного и того же g Доказательство того, что 3x² - 20x - 1 является Theta(x²) с 4x² сверху и 2x² снизу Почему нижняя граница исключает более быстрорастущие кандидаты, такие как 2^x и x³ Рецепт: сохранить доминирующий член, отбросить его константу и каждый второй член Нет слишком большой аддитивной константы и нет слишком малого коэффициента, чтобы его игнорировать Запись ответа в собственной входной переменной функции, не всегда N Функции с двумя входными данными: ответ зависит от того, какой входной параметр изменяется Theta(1) для параметра, который не появляется в стоимости в точке все ━━━━━━━━━━━━━━━━━━━━━━━━━ ИСТОЧНИКИ МАТЕРИАЛОВ Источники для этого видео взяты с    • Lecture 22: Big Oh and Theta