Алгоритм анализа, Big O Notation Домашнее задание

Question

Привет, может кто-нибудь объяснить мне, как решить эту домашнюю работу? (n + log n) 3 ^ n = O ((4 ^ n) / n). я думаю, что это то же самое, что и решение этого неравенства: (n + log n) 3 ^ n

заранее спасибо

Answer 1

По определение , f(n) = O(g(n)) истинно, если существует постоянная M такая, что |f(n)| < M|g(n)| для каждого n. В информатике числа неотрицательны, так что это равносильно нахождению M такого, что f(n) / g(n) < M

Это, в свою очередь, можно сделать, доказав, что f(n) / g(n) имеет конечный предел при увеличении n к бесконечности (по определению предела). Что в случае вашего (n^2 + n log n) * (3/4)^n довольно очевидно в силу того, как работают экспоненциальные функции.

Answer 2

Вам нужно найти c (как вы упомянули в своей задаче), и вам нужно показать, что неравенство выполняется для всех n, больших k.

Показав, что вы можете найти рассматриваемые c и k, тогда по определению вы доказали границу big-O.

И наоборот, если вы не можете найти такие c и k, это потому, что функция слева не ограничена сверху функцией справа. Это не должно иметь место, хотя (и вы будете знать, что вы получаете более интуитивное понимание асимптотического роста / ограничения, когда вы можете точно сформулировать, почему).