Функция масштабирования большой o (n+1)^5 / 4n^2

Question

Я расширил (n+1)^5: (n^5+5n^4+10n^3+10n^2+5n+1)/4n^2

упростили и приказали им быть:

n ^ 3/4 + 5n ^ 2/4 + 1 / 4n ^ 2 + 10n / 4 + 5 / 4n + 10/4

Я обнаружил, что если я подключу 6 для тестирования, то сначала он удовлетворяет двум:

• п ^ 5 / 4n ^ 2 = 216/4
• 5n ^ 4 / 4n ^ 2 = 180/4

но в остальном это не соответствует правилам, основанным на большой шкале сложности. также из 5n ^ 4 / 4n ^ 2 я не знаю, куда двигаться дальше, с точки зрения их упорядочения.

так что это правильно: n^3/4 + 5n^2/4 + 1/4n^2 + 10n/4 + 5/4n + 10/4.

Затем я подключаю 6, если я не подключаю это и получаю:

216/4 >> 180/4 >> 1/44 >> 60/4 >> 5/24 >> 5/2.

тогда напишите это fn=O(n^3) для ответа и все?

Answer 1

Подсказка:

1. используя свои школьные навыки алгебры, поверните (n^5+5n^4+10n^3+10n^2+5n+1)/4n^2 в простой полином

2. используя свои навыки алгебры в средней школе, определите термин в полиноме, который растет быстрее всего, как n стремится к бесконечности (то есть "становится большим")

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

Вы не пытаетесь решить это уравнение для n, Не в этом дело.

Смысл сложного анализа состоит в том, чтобы понять, как функция стоимости растет n становится большим. Цель (неформально) - выяснить, чему функция пропорциональна. Графики - это один (неформальный) способ сделать это.

Ответ... когда вы решите это... будет что-то вроде O(n^p), Всего один термин. Судя по вашим вопросам / комментариям, вы, похоже, не понимаете, что именно вы пытаетесь решить здесь.

Я предлагаю вам также вернуться к своим конспектам лекций или учебникам, чтобы найти определение большой сложности. Или прочитайте это:

• Что такое простое английское объяснение обозначения "Big O"?
• https://en.wikipedia.org/wiki/Big_O_notation

^{(Вы также можете сделать это математически строго; т.е. с помощью индуктивного доказательства и формального определения} big O ^{нотации. Но если вы не делаете это как часть курса математики университетского уровня, они, вероятно, не ожидают такого уровня строгости.)}

Answer 2

Числитель - это многочлен степени 5, знаменатель - это многочлен степени 2.

По сложности это приводит прямо к ответу 5 - 2 = 3, или, другими словами, n^3

Например, используйте полиномиальное длинное деление, чтобы убедить себя в этом. Но иначе знайте, что степени могут быть немедленно вычтены таким образом, когда дело доходит до полиномиальной сложности.

Если бы вы построили график вашей начальной полиномиальной дроби и "расширили" представление, чтобы увидеть все больше и больше положительных значений n, график будет все больше и больше походить на график n^3 ...