使用 Big-O 表示法的数量级

Question

这可能是已经涵盖的基础，但我还没有找到我能够理解的解释。估计很快就尴尬了。

例如，我正在尝试使用以下大 O 表示法找到数量级：

count = 0;
for (i = 1; i <= N; i++)
    count++;

我从哪里开始找到定义幅度的因素？我的数学相对较差，尽管我尝试了一些资源，但还没有找到可以解释一段代码转换为代数方程的方式的东西。坦率地说，我什至无法猜测关于这个循环的 Big-O 效率是多少。

Answer 1

你的例子就是订单

O(N)

其中N=number of elements，并且对每个进行比较计算，因此

for (int i=0; i < N; i++) {
    // some process performed N times
}

大 O 表示法可能比您想象的要简单；在所有日常代码中，您会在循环、列表迭代、搜索和任何其他确实对每个集合中的个体工作一次的过程中找到 O(N) 的示例。是先不熟的抽象，O(N)表示"some unit of work"，重复N次。这个 "something" 可以是一个递增计数器，如您的示例所示，或者它可以是冗长且资源密集型的计算。大多数时候，在算法设计中，'big-O' 或复杂性比工作单元更重要，当 N 变大时，这一点尤其重要。 'limiting' 或 'asymptotic' 的描述在数学上很重要，这意味着无论工作单元多么重要，复杂度较低的算法总是会击败复杂度较高的算法 ，假设 N 足够大，或者 "as N grows"

再举个例子，理解大意

for (int i=0; i < N; i++) { for (int j=0; j < N; j++) { // process here NxN times } }

这里的复杂度是

O(N²)

例如，如果 N=10，则第二个 "algorithm" 将花费比第一个长 10 倍的时间，因为 10x10 = 100（= 大十倍）。如果你考虑当 N 等于一百万或十亿时会发生什么，你应该能够计算出它 也将花费更长的时间 。所以如果你能找到一种方法在 O(N) 中做某事，就像一台超级计算机在 O(N²) 中做的那样，你应该能够用你的旧 x386 打败它，怀表，或其他旧工具

Answer 2

这些符号（大 O、大 omega、theta）只是说明当事情变得越来越大时，算法将如何 "difficult"（或复杂）渐近。

对于大 O，有两个函数：f(x) 和 g(x) 其中 f(x) = O(g(x)) 然后你可以说你能够找到一个 x 从 g (x) 总是大于 f(x)。这就是为什么定义包含 "asymptotically" 的原因，因为这两个函数可能在开头有任何运行（例如 f(x) > g(x) 对于少数第一个 x）但是从单个点开始，g (x) 总是会变得更好 (g(x) >= f(x))。因此，您对 long 运行中的行为感兴趣（不仅仅针对小数字）。有时大 O 符号被命名为上界，因为它描述了最坏的可能情况（它永远不会比这个函数更难）。

那是"mathematical"部分。在练习时，您通常会问：算法必须处理多少次？将进行多少次操作？

对于你的简单循环，这很容易，因为随着你的 N 的增长，算法的复杂度将线性增长（作为简单的线性函数），所以复杂度为 O(N)。对于 N=10，您将必须执行 10 次操作，对于 N=100 => 100 次操作，对于 N=1000 => 1000 次操作...所以增长是真正线性的。

我再举几个例子：

for (int i = 0; i < N; i++) {
   if (i == randomNumber()) {
      // do something...
   }
}

这里好像复杂度会低一些，因为我在循环中加入了条件，所以我们有可能"doing something"操作的次数会少一些。但是我们不知道条件会通过多少次，它可能每次都通过，所以使用 big-O（最坏情况）我们再次需要说复杂度是 O(N).

另一个例子：

for (int i = 0; i < N; i++) {
   for (int i = 0; i < N; i++) {
       // do something
   }
}

这里随着N越来越大，#of operations会增长的更快。 N=10 意味着您必须执行 10x10 次操作，N=100 => 100x100 次操作，N=1000 => 1000x1000 次操作。你可以看到增长不再是线性的，它是 N x N，所以我们有 O(N x N)。

对于最后一个例子，我将使用满二叉树的思想。希望你知道什么是二叉树。那么如果你对根有一个简单的引用，你想遍历它到最左边的叶子（从上到下），如果这棵树有 N 个节点，你需要做多少次操作？该算法类似于：

Node actual = root;
while(actual.left != null) {
   actual = actual.left
}
// in actual we have left-most leaf

您需要执行多少操作（循环将执行多长时间）？这取决于树的深度，对吧？全二叉树的深度是如何定义的？它类似于 log(N) - 对数的底数 = 2。所以在这里，复杂度为 O(log(N)) - 通常我们不关心对数的底数，我们关心的是函数（线性、二次、对数...）

使用 Big-O 表示法的数量级

Order of magnitude using Big-O notation

algorithm

big-o

magnitude