使用Big的数量级
这个问题在这里已经有了答案：
这些符号（大O，大Omega，theta）简单地说，当事情变得越来越大时，算法如何渐近“困难”（或复杂）。
对于大O，有两个函数：f（x）和g（x），其中f（x）= O（g（x）），那么你可以说你能找到一个x，g（x）将是总是大于f（x）。 这就是为什么定义包含“渐近”的原因，因为这两个函数可能在开始时有任何运行（例如对于少数第一个x，f（x）> g（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×N，所以我们有O（N×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）） - 通常我们不关心对数的基数，我们关心的是函数（线性，二次，对数...）
你的例子是订单
上）
其中N=number of elements ，并且因此对每个N=number of elements执行可比较的计算
for (int i=0; i < N; i++) {
// some process performed N times
}
大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（N2）
例如，如果N = 10，那么第二个“算法”将比第一个长10倍，因为10x10 = 100（=十倍大）。 如果你考虑一下N等于什么时候会发生什么，比如说一百万或者十亿，那么你应该能够计算出它会花费更长的时间。 所以，如果你可以找到一种方式去做O（N）中的超级计算机在O（N2）中做的事情，那么你应该可以用旧的x386，怀表或其他旧工具来击败它
链接地址: http://www.djcxy.com/p/39349.html上一篇: Order of magnitude using Big
下一篇: algorithm