Имеется функция вида $$n^{2}-6n+5$$

Надо оценить ее порядок. Автор написал в ответе, что порядок О(n^{3}) Объясните, пжл, как это считать. Тут же есть пример с таким же порядком $$n(ln(n))^{2}$$

задан 24 Апр '12 14:06

10|600 символов нужно символов осталось
0

Формально это правильно, хотя обычно так не пишут. $% 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$%.
Аналогично, во втором примере $%|\frac{n \cdot (ln(n))^2}{n^3}| \leq c \sim \frac{(ln(n))^2}{n^2} \leq c \sim (\frac{ln(n)}{n})^2 \leq c $%, что тоже верно.

Но еще раз повторяю, обычно при использовании O-большого имеют в виду двойное неравенство$%с_1 \leq |\frac{f_n}{g_n}| \leq c_2$% с положительным (а не нулевым!) $%c_1 $% .
Если же такое неравенство возможно только при $%c_1=0 $%, то используют o-малое.

ссылка

отвечен 24 Апр '12 14:47

изменен 24 Апр '12 15:35

Я видел следующее в интернете. Там задача решается так. Берут и пишут неравенство $$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
10|600 символов нужно символов осталось
0

А Вы не путаете прописные и строчные буквы? Есть понятие "о-малое" и "О-большое". Первое означает "бесконечно малое по сравнению с...", а второе - "одного порядка с ...".
В вашем случае $%n^2-6n+5=o(n^3),$% но $%n^2-6n+5=O(n^2).$% при $%n\to+ \infty $%.

ссылка

отвечен 24 Апр '12 14:10

Вот, о чем и речь. Я не путаю, меня это смутило донельзя, тк до этого не было ошибок в ответах. А подскажите, если можно, как со вторым быть? как понять, что оно верно?

(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
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×35

задан
24 Апр '12 14:06

показан
2568 раз

обновлен
24 Апр '12 19:32

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru