algorithm - 大 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 进行测试它首先满足两个:

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

但对于其余部分，它不符合基于大 o 复杂性规模的规则。同样从 5n^4/4n^2 开始，我不知道从那里移动到哪里，就订购而言。

所以这是正确的:n^3/4 + 5n^2/4 + 1/4n^2 + 10n/4 + 5/4n + 10/4。

然后我插入 6 如果我不插入 is 并得到:

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)。就一个学期。根据您的问题/评论，您似乎不明白您要在这里解决的问题。

我建议您也回到您的讲义或课本中查找大 O 复杂性的定义。或者阅读这些:

• What is a plain English explanation of "Big O" notation?
• https://en.wikipedia.org/wiki/Big_O_notation

^{(您也可以采用数学上严格的方式进行；即使用归纳证明和 big O 符号的正式定义。但除非您将此作为大学的一部分进行级别的数学类(class)，他们可能不期望那么严格。)}