4

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

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

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

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

4

2 回答 2

2

你的例子是订单

上）

其中N=number of elements, 并且对每个都执行可比较的计算，因此

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

big-O 符号可能比您想象的要容易。在所有日常代码中，您都会在循环、列表迭代、搜索和任何其他对集合中的每个个体都有效的过程中找到 O(N) 的示例。最初不熟悉的是抽象，O(N) 的意思是“某个工作单元”，重复了 N 次。这个“东西”可以是一个递增的计数器，就像你的例子一样，也可以是冗长且资源密集型的计算。大多数时候，在算法设计中，“大 O”或复杂性比工作单元更重要，当 N 变大时，这一点尤其重要。“限制”或“渐近”的描述在数学上很重要，这意味着无论工作单元多么重要，复杂度较低的算法总是会击败更大的算法，假设 N 足够大，或者“随着 N 的增长”

再举一个例子，了解大意

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

这里的复杂性是

O(N 2 )

例如，如果 N=10，那么第二个“算法”将比第一个长 10 倍，因为 10x10 = 100（= 大十倍）。如果你考虑当 N 等于一百万或十亿时会发生什么，你应该能够计算出它也需要更长的时间。因此，如果您能找到一种方法在 O(N) 中完成超级计算机在 O(N 2 ) 中所做的事情，那么您应该能够使用旧的 x386、怀表或其他旧工具来击败它

于 2015-09-03T00:02:17.030 回答
2

这些符号（大 O，大欧米茄，θ）只是说明当事情变得越来越大时，算法将如何渐近地“困难”（或复杂）。

对于大 O，有两个函数：f(x) 和 g(x) 其中 f(x) = O(g(x)) 那么你可以说你能够找到一个 x 从中 g(x)总是大于 f(x)。这就是为什么定义包含“渐近”的原因，因为这两个函数可能在开始时有任何运行（例如 f(x) > g(x) 对于少数第一个 x）但是从单点开始，g(x) 将始终优越（g（x）> = f（x））。所以你对长期的行为感兴趣（不仅仅是小数字）。有时大 O 表示法被命名为上限，因为它描述了最坏的可能情况（它永远不会比这个函数更困难）。

那是“数学”部分。在实践中，您通常会问：算法需要处理多少次？会做多少操作？

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

我再举几个例子：

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

这里似乎复杂性会更低，因为我在循环中添加了条件，所以我们有可能“做某事”操作的数量会更低。但是我们不知道条件会通过多少次，它可能每次都通过，所以使用 big-O（最坏的情况）我们再次需要说复杂度是 O(N)。

另一个例子：

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

在这里，随着 N 越来越大，操作数将增长得更快。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)) - 通常我们不关心对数的底数，我们关心的是函数（线性、二次、对数...）

于 2015-09-03T05:43:34.023 回答