今天我遇到了 msdn 中的博客，我注意到如何计算算法的时间复杂度。我完全理解如何计算算法的时间复杂度，但最后作者提到了以下几行
把我得到的所有东西都加起来
(N+4)+(5N+2)+(4N+2) = 10N+8
所以上面代码的渐近时间复杂度是O(N)，也就是说上面的算法是线性时间复杂度算法。
那么作者怎么会说它是基于线性时间复杂度算法的。博客的链接
问问题
1759 次
5 回答
7
他说因为10N+8是一个线性方程。如果你画出这个方程，你会得到一条直线。尝试10 * x + 8在此网站上输入（功能图）并亲自查看。
于 2012-05-11T07:08:49.800 回答
0
一个非常务实的规则是：
当算法 si 的复杂度由 poly 表示时，复杂度的A*n^2+B*n+C 阶数 （即 O(something) ）等于变量 n 的最高阶。
在A*n^2+B*n+Cpoly 中，顺序为 O(n^2)。
就像 josnidhin 解释的那样，如果 poly 有
- 1阶（即n）-称为线性
- 2 阶（即 n^2） - 称为二次
- ... 等等。
于 2012-05-11T08:23:14.043 回答
0
笔者只是根据自己的经验选择了最合适的。您应该知道，计算算法的复杂性几乎总是意味着要找到一个Big-Oh函数，而该函数又只是给定函数的上限（在您的情况下为10N+8）。
只有几种众所周知的复杂度类型：线性复杂度、二次复杂度等。因此，计算时间复杂度的最后一步包括选择可用于给定函数的不太复杂的类型（我的意思是，线性比二次复杂，二次比指数复杂，依此类推） ，它正确地描述了它的复杂性。
在您的情况下， O(n) 和 O(n^2) 甚至 O(2^n) 确实是正确的答案。但是，在Big-Oh 符号定义中完全适合的不太复杂的函数是O(n)，这是这里的答案。
这是一篇真正的好文章，充分解释了Big-Oh 符号。
于 2012-05-11T07:12:13.220 回答
0
时间复杂度升序（常见的）
O(1) - Constant
O(log n) - logarithmic
O(n) - linear
O(n log n) - loglinear
O(n^2) - quadratic
注：N 无限增加
于 2012-05-11T07:14:08.690 回答
0
对于复杂性理论，您绝对应该阅读一些背景理论。它通常是关于渐近复杂度的，这就是为什么你可以删除较小的部分，只保留复杂度类。
N关键思想是，和N+5变得可以忽略不计之间的差异N真的很大。
有关更多详细信息，请从此处开始阅读：
于 2012-05-11T07:16:58.477 回答