0
Я пытаюсь доказать, что n^2 + 5 log (n) = O (n^2), O - обозначение большой O. Я не очень хорош с доказательствами, и любая помощь будет оценена по достоинству.Докажите, что n^2 + 5 log (n) = O (n^2)
A
ответ
1
Неофициально, мы принимаем значение big-O как самый быстрорастущий термин, поскольку n растет сколь угодно большим. С n^2 растет намного быстрее, чем log (n), это должно быть ясно.
Более формально asymptotic behaviors идентичны, когда предел отношения двух функций приближается к 1 в качестве параметра (-ов) подхода (-ов) к бесконечности, который должен звучать как одно и то же. Итак, вам нужно будет показать, что lim (n-> inf) ((n^2 + 5log (n))/n^2) = 1.
Подсказка: выделите * самый быстрорастущий компонент * с левой стороны (либо неявно, либо явно) - (нотация Big O) [https://en.wikipedia.org/wiki/Big_O_notation] принимает только * быстро развивающийся * компонент. Вы также можете доказать это, например. решая предел 'lim n-> inf LEFT_SIZE/PROPOSED_RIGHT_SIZE = 1' (доказательство того, что ИМО является достаточным доказательством того, что при большом значении O в порядке), путем нахождения асимптотической границы и т. д. – vaxquis
Самый простой способ доказать это просто показать, что 5 log (n) меньше n^2. Тогда n^2 + 5 log (n) меньше 2n^2, тогда n^2 + 5 log (n) равно O (n^2) –