5

我错过了介绍 big-O 的课程，认为它非常简单。然而，当 n 变得非常小时，老师似乎仍然说了一些关于 O(n) 偏离函数的内容？我在书中的任何地方都找不到这个。有人可以启发我吗？我们对 O(n) 的探索是在排序算法的背景下进行的，如果这有任何意义的话。

谢谢基因

编辑：感谢它一直以来的帮助。我有一个后续问题。是否有一种相对简单的数学方法来找出 n 对于 O(n) 而言太小的点？

相关问题

是否有任何 O(1/n) 算法？
Θ(n) 和 O(n) 有什么区别？

4

7 回答 7

22

Big O 没有描述函数的执行时间，只是描述了增长。所有函数都有一些需要添加的常数因子或开销。当 n 较低时，这种开销可能会使算法的任何改进大大相形见绌 - 每次操作需要 50ms 但具有 O(n) 的算法对于较小的 n 会执行得更差比每次操作需要 5 毫秒但有 O(n*n) 的算法。

这就是为什么，一般来说，对于小集合，大 O 并不重要。对于大多数具有简单比较的对象，对 10 个项目的快速排序不会明显比冒泡排序快，对 100 个项目的线性搜索可能会比二叉树快，等等。

于 2009-05-08T23:34:47.587 回答
11

Big-O 符号背后的概念是算法的渐近性能。随着 N 变大，Big-O 表示法中的项开始支配总时间。例如，在 O(N^2) 算法中，总时间 T(N) 可能是：

T(N) = a * N * N + b * N + c

随着 N 越来越大，无论 b 或 c 的值如何，N^2 中的项都占主导地位。

但是，当 N 很小时，b 和 c 项很重要。

例如，如果 a = 0.001、b = 1,000 和 c = 1,000,000。

 N                ~ T(N) [1 significant figure]
 1                1,000,000                (almost all c)
 1,000            2,000,000                (50:50 split on b and c)
 1,000,000        2,000,000,000            (50:50 split on a and b)
 1,000,000,000    1,000,000,000,000,000    (almost all a)

因此，如果您忽略低阶项，则低 N 的性能将被完全歪曲。在高 N 时，低阶项无关紧要。

于 2009-05-08T23:47:39.177 回答
8

随着参加的讲座数量（N）变得非常少，课程材料变得更难理解。

于 2009-05-08T23:39:55.157 回答
2

也许以下是“当 n 变得非常小时 O(n) 偏离函数”的示例：

例如，考虑一个需要时间“50 乘以 n，加上 n 的平方”的操作。

当 n 很大时，“n 平方”项将占主导地位，因此该操作可以说是“O(n 平方)”。

然而，当 n 很小时，“n 平方”项将可以忽略不计，“50 倍 n”项将占主导地位，因此当（且仅当）n 很小时，它可以说是 O(n) .

于 2009-05-08T23:40:55.513 回答
1

为了扩展上述答案，Big-Oh 表示法测量函数的最终增长或其限制行为。

f = O(g) 当且仅存在一个 N 和一个常数 c（它可以是 N 的函数）使得对于所有 n > N，
f(n) <= c*g(n)

假设 f = 10000000*n 和 g = n^2。

f = O(g)，但是如果你看 n 的值太小，比如小于 10000000 并设置 c = 1，你会看到 g(n) <= f(n)。

再举一个更极端的例子，你宁愿处理复杂度为 n^100000 的算法还是复杂度为 2^(.0000000001n) 的算法。对于合理的问题大小，后者更好。使很多 CS 如此美丽的原因在于它允许这种类型的滥用，但是，大多数自然算法都没有利用它。大多数多项式时间算法都有小常数（至少经过一些工作）。

祝你好运！

于 2009-05-08T23:44:05.973 回答
0

根据定义：
f(n)= Θ(g(n))表示所有函数 f(n)的集合，因此需要有常数c1和c2以及n0，其中所有这些情况都为真：

  • c1。g(n)是一个非负项或 0。
  • c1。g(n) <= f(n) [g(n) 需要是某个 n 的下限]
  • f(n) <= c2 。g(n) [g(n) 也需要是上限，因为我们正在定义 Θ]。
  • 对于所有大于我们选择的 n0 的 n

所以我们需要做的就是选择一个使所有条件都为真的 c1、c2 和 n0。因此，对于 c1 c2 的某些组合，如果您选择 n < n0，则不能保证您的绑定有效。我想这就是你老师所说的“偏差”。

于 2009-05-25T11:39:59.917 回答
0

一个很大的题外话，但为了完整起见，我想提一些其他的符号，它们与 Big_o 符号相关，通常用于理论计算机科学，您可能会在计算机科学文献中找到这些符号：Big-Θ 符号，the Big-Θ notation，the Big-Ω 符号和 little-o 符号。这些只是对增长率的其他（更严格的）描述。little-o 表示法很容易被误认为是 big-O 表示法。

little-o 也是两个函数 f(x) 和 g(x) 之间的关系。说 'f(x) is little-o of g(x)' 意味着 f(x) 比 g(x) 增长得快得多。用更多的数学术语来说，当 x 接近无穷大时，f(x)/g(x) 的极限为零。

正如前面的答案中提到的，big-O 表示法用于描述算法增长率的上限。它实际上是两个函数 f(x) 和 g(x) 之间的关系，其中 f(x) = O(g(x)) 随着 x 趋于无穷大。

请参阅Big-o 维基百科页面，以获得对不同符号的简洁明了的介绍。

于 2009-05-13T06:46:45.443 回答