Имеется функция вида $$n^{2}-6n+5$$ Надо оценить ее порядок. Автор написал в ответе, что порядок О(n^{3}) Объясните, пжл, как это считать. Тут же есть пример с таким же порядком $$n(ln(n))^{2}$$ задан 24 Апр '12 14:06 RootKit |
Формально это правильно, хотя обычно так не пишут. $% f_n=O(g_n) $% означает $%|\frac{f_n}{g_n}|\leq M, при \; n \rightarrow \infty$%. Но обычно при такой записи подразумевается, что не только $% f_n=O(g_n) $%, но и $% g_n=O(f_n) $%, в противном случае используется o-малое. То же самое можно сказать и о втором примере. Ответ на комментарий. Все правильно, можно, конечно писать $% n^2-6n+5 \leq c \cdot n^3 $%, но лучше $%|\frac{n^2-6n+5}{n^3}| \leq c \sim |\frac{n^2}{n^3}| \leq c \sim \frac{1}{n} \leq c$%. Но еще раз повторяю, обычно при использовании O-большого имеют в виду двойное неравенство$%с_1 \leq |\frac{f_n}{g_n}| \leq c_2$% с положительным (а не нулевым!) $%c_1 $% . отвечен 24 Апр '12 14:47 Андрей Юрьевич Я видел следующее в интернете. Там задача решается так. Берут и пишут неравенство $$n^{2}-6n + 5 < c*n^{3}$$ и смотрят правильное оно или нет. Я воспользовался этим примером, посчитал.. все правильно. но тут я увидел такой пример $$n^{2}\left(ln(n) \right)$$. по логике с неравенством он очевидно верен, но автор утверждает обратное. как так?
(24 Апр '12 14:57)
RootKit
Все то же самое. В чем вопрос?
(24 Апр '12 16:15)
Андрей Юрьевич
Объяснение вверху для меня было просто великолепным, спасибо Вам большое.
(24 Апр '12 19:32)
RootKit
|
А Вы не путаете прописные и строчные буквы? Есть понятие "о-малое" и "О-большое". Первое означает "бесконечно малое по сравнению с...", а второе - "одного порядка с ...". отвечен 24 Апр '12 14:10 DocentI Вот, о чем и речь. Я не путаю, меня это смутило донельзя, тк до этого не было ошибок в ответах. А подскажите, если можно, как со вторым быть? как понять, что оно верно?
(24 Апр '12 14:15)
RootKit
Запись $%f(x)=O(g(x))$% означает, что отношение $%f(x)\over g(x)$% ограничено. Поделите $%n^2-6n+5$% на $%n^2$% и оцените дробь (при больших n). Вообще-то известно, что многочлен в бесконечности асимптотически равен своему старшему слагаемому. Значит, они одного порядка и одно ограничено относительно другого.
(24 Апр '12 14:19)
DocentI
|