我正在学习 CLRS 书，学习 big-O 分析的第一个示例涉及一个从数组 A 的第二个元素到最后一个元素（第 26 页）的 for 循环，但它将时间成本归因于这条线为“n”。
我不明白为什么它不是n-1。如果我有一个大小为 5 (n=5) 的数组 A，并且我的 for 循环从 A[1] 到 A[4]，则总共有 4 次迭代，或 n-1。
它实际上是 n 的成本，因为它需要进行最后一次检查以确保它退出 for 循环或其他什么？
问问题
69 次
5 回答
1
这是因为他们试图展示 Big-O 分析的全部内容——它是关于“大”图的。通常的数学解释是这样的：给定足够大的 n 值，常数项的加法或减法对于算法复杂性的分析是无关紧要的。
简单来说，如果一个数组包含美国等国家公民的人口统计信息，则该数组的大小超过 300,000,000 个元素。在比较算法时，您会关心算法进行了 299,999,999 次计算还是 300,000,000 次计算？
您也可以将其视为四舍五入，为了简单和清晰起见，将不显着的小数字剪掉。
于 2013-03-22T19:48:16.333 回答
0
在进行 Big-O 表示法时，O(n) 和 O(n - 1) 本质上是相同的。当 n 达到无穷大时，O(n) 和 O(n - 1) 的速度大致相同。-1 可以忽略不计。Big O 分析通常会在参数接近无穷大时检查函数的复杂性。
于 2013-03-22T19:45:02.753 回答
0
不要将 big-O 视为迭代次数的精确计数。循环的运行时间与 n 成正比。在您的示例中，如果您将数组中的元素数量加倍，那么您的运行时也将大约加倍。如果有帮助，请始终考虑如果大幅增加 n 会发生什么。
于 2013-03-22T19:47:24.267 回答
0
是的，处理n-1数组元素的 for 循环是 O(n-1)，但它也是 O(n)。考虑正式定义：
f(x) = O(g(x))当且仅当存在一个正实数M和一个实数x0使得|f(x)| ≤ M·|g(x)|所有x > x_0.
很明显，如果常量Mandx0与 一起使用g(x)=x-1，那么 Mandx0也将与g(x)=x.
在大 O 表示法O(g(x))中，习惯上忽略多项式 g(x) 的低阶项，因为随着x变大，前导项总是占主导地位。更具体地说，如果第一个低阶项是负号（与 一样g(x)=x-1），我们不需要找到M和的新值x0。如果该项为正号，则乘以M第二项的系数会得到一个M在删除第二项的情况下工作的值。这在wikipedia中有更详细的解释。
于 2013-03-22T20:30:13.650 回答
0
复杂性分析用于推断一般计算的行为方式。一种方法是推理越来越大的输入值（趋于无穷大）。
假设您的实际计算是某个函数f(n) = 3n + 10
现在让有另一个函数，g(n) = 5n + 15
由于n趋于无穷大并且您将两个函数绘制在一起，它们之间的比率趋于一个常数。因此，比率趋于常数的函数被认为具有相似的复杂度，属于同一复杂度类。
f(n)属于O(n)的类，就像g(n)一样。编辑：澄清。这就是人们在非正式场合谈论复杂性时通常所说的意思。要更深入地了解所有不同类型的渐近线，请查看此答案末尾的链接。
现在，另一方面，如果g(n) = 2^n，那么它们之间的比率不会趋于恒定，因此它们不会属于同一复杂度类别。
作为自己的练习，想想f(n) = log_2(n)和g(n) = log_3(n)的比率如何工作。
最后一点：big-Oh 有更严格的定义。它被认为是一个上限。所以，如果你的函数是一个常数，比如f(n) = 5，f仍然是O(n)。您应该研究整个渐近函数系列以更深入地了解。
于 2013-03-22T22:45:40.447 回答