Как доказать обозначение Big O
В моем классе алгоритма мы обсуждаем нотацию больших О, и я застрял, доказывая эту примерную проблему:
доказывать f(n) = 3n lg n + 10n + lg n + 20 = O(n lg n)
Детали будут оценены.
Решение
Big O нотация является асимптотическое обозначение и это все о приближении случаев (худший, лучший и средний).
В вашем примере nlgn растет быстрее, чем оба n а также lgnБолее того, постоянные значения не имеют значения и могут быть проигнорированы в таком приближении.
Из этого следует, что сложность O(nlgn),
Другие решения
Все, что вам нужно доказать, это то, что для некоторых M и X0:
M n lg n> = 3n lg n + 10n + lg n + 20 для всех n больше X0
4 довольно легко для М
Я уверен, что вы можете вычислить некоторый x0, для которого выполняется указанное выше неравенство, а затем легко показать, что он остается верным для всех n, больших, чем X0
Это помогает упростить вышесказанное после замены в 4
(n-1) lg n> = 10n + 20
Если любое n достаточно велико, должно быть ясно, что lg n> 1, поэтому любое увеличение n за пределами этого увеличивает правое на 1, а левое более чем на 1.