大O，你如何计算/估计它？
大多数拥有CS学位的人肯定知道Big O代表什么。 它可以帮助我们衡量一个算法的真实效率，并且如果你知道你试图解决的问题存在于哪个类别中，你可以计算出它是否仍然可以排除那些额外的性能。
但我很好奇，你如何计算或近似算法的复杂性？
1，但正如他们所说，不要过头，过早优化是所有邪恶的根源，没有合理原因的优化也应该得到这个名称。
我是当地大学的数据结构和算法课程的助教。 我会尽我所能在这里简单地解释它，但要警告的是，这个话题需要我的学生几个月才能最终掌握。 您可以在Java书中找到关于数据结构和算法第2章的更多信息。
没有可用于获得BigOh的机械程序。
作为一本“食谱”，为了从一段代码中获得BigOh，你首先需要认识到你正在创建一个数学公式来计算在给定一定尺寸的输入的情况下计算多少个步骤。
目的很简单：从理论角度比较算法，而不需要执行代码。 步数越少，算法越快。
例如，假设您有这段代码：
int sum(int* data, int N) {
int result = 0; // 1
for (int i = 0; i < N; i++) { // 2
result += data[i]; // 3
}
return result; // 4
}
该函数返回数组中所有元素的总和，我们想创建一个公式来计算该函数的计算复杂度：
Number_Of_Steps = f(N)
所以我们有f(N) ，这是一个计算计算步数的函数。 函数的输入是要处理的结构的大小。 这意味着这个函数被调用，例如：
Number_Of_Steps = f(data.length)
参数N取data.length值。 现在我们需要函数f()的实际定义。 这是从源代码完成的，其中每条有趣的行从1到4编号。
有很多方法可以计算BigOh。 从这一点开始，我们将假设每一个不依赖于输入数据大小的句子都需要一个恒定的C数字计算步骤。
我们将添加函数的单个步数，局部变量声明和返回语句都不依赖于data数组的大小。
这意味着第1行和第4行每个步骤需要C个步骤，并且函数有点像这样：
f(N) = C + ??? + C
接下来的部分是定义for语句的值。 请记住，我们正在计算计算步骤的数量，这意味着for语句的主体会被执行N次。 这与添加C ， N次相同：
f(N) = C + (C + C + ... + C) + C = C + N * C + C
没有机械规则来计算for的主体执行的次数，您需要通过查看代码执行的操作来计算它的次数。 为了简化计算，我们忽略了for语句的变量初始化，条件和增量部分。
为了得到实际的BigOh，我们需要函数的渐近分析。 这大致是这样做的：
C f()得到standard form的多项式。 N接近infinity时，保持那个变大的那个。 我们的f()有两个术语：
f(N) = 2 * C * N ^ 0 + 1 * C * N ^ 1
带走所有C常数和冗余部分：
f(N) = 1 + N ^ 1
由于最后一项是当f()接近无穷大时（思考极限）时变得更大的那个，所以这是BigOh参数，并且sum()函数具有BigOh：
O(N)
有一些技巧可以解决一些棘手的问题：只要有可能就使用求和。
作为一个例子，这个代码可以使用求和来轻松解决：
for (i = 0; i < 2*n; i += 2) { // 1
for (j=n; j > i; j--) { // 2
foo(); // 3
}
}
你需要问的第一件事是执行foo()的顺序。 虽然通常是O(1) ，但您需要向教授咨询。 O(1)表示（几乎大部分）恒定的C ，与大小N无关。
在for上句号码声明是一个棘手。 索引以2 * N结尾，增量为2。 这意味着，第一for被执行仅N步骤，我们需要除以2计数。
f(N) = Summation(i from 1 to 2 * N / 2)( ... ) =
= Summation(i from 1 to N)( ... )
第二句更加棘手，因为它取决于i的价值。 请看：索引i取值为：0，2，4，6，8，...，2 * N，而第二for得到执行：N次的第一个，N - 2，第二，N - 4，第三...到N / 2阶段，在其上第二for永远不会被执行。
在公式上，这意味着：
f(N) = Summation(i from 1 to N)( Summation(j = ???)( ) )
同样，我们正在计算步数 。 根据定义，每个求和总是应该从1开始，并以大于或等于1的数字结束。
f(N) = Summation(i from 1 to N)( Summation(j = 1 to (N - (i - 1) * 2)( C ) )
（我们假设foo()是O(1)并采取C步骤。）
这里我们遇到了一个问题：当i向上取值N / 2 + 1时，内部Summation以负数结束！ 这是不可能的和错误的。 我们需要将总和分成两部分，这是i拿N / 2 + 1的关键时刻。
f(N) = Summation(i from 1 to N / 2)( Summation(j = 1 to (N - (i - 1) * 2)) * ( C ) ) + Summation(i from 1 to N / 2) * ( C )
由于关键时刻i > N / 2时，内for不会得到执行，并且我们假定在其主体上的常数C的执行的复杂性。
现在可以使用一些身份规则来简化总和：
w无关） 应用一些代数：
f(N) = Summation(i from 1 to N / 2)( (N - (i - 1) * 2) * ( C ) ) + (N / 2)( C )
f(N) = C * Summation(i from 1 to N / 2)( (N - (i - 1) * 2)) + (N / 2)( C )
f(N) = C * (Summation(i from 1 to N / 2)( N ) - Summation(i from 1 to N / 2)( (i - 1) * 2)) + (N / 2)( C )
f(N) = C * (( N ^ 2 / 2 ) - 2 * Summation(i from 1 to N / 2)( i - 1 )) + (N / 2)( C )
=> Summation(i from 1 to N / 2)( i - 1 ) = Summation(i from 1 to N / 2 - 1)( i )
f(N) = C * (( N ^ 2 / 2 ) - 2 * Summation(i from 1 to N / 2 - 1)( i )) + (N / 2)( C )
f(N) = C * (( N ^ 2 / 2 ) - 2 * ( (N / 2 - 1) * (N / 2 - 1 + 1) / 2) ) + (N / 2)( C )
=> (N / 2 - 1) * (N / 2 - 1 + 1) / 2 =
(N / 2 - 1) * (N / 2) / 2 =
((N ^ 2 / 4) - (N / 2)) / 2 =
(N ^ 2 / 8) - (N / 4)
f(N) = C * (( N ^ 2 / 2 ) - 2 * ( (N ^ 2 / 8) - (N / 4) )) + (N / 2)( C )
f(N) = C * (( N ^ 2 / 2 ) - ( (N ^ 2 / 4) - (N / 2) )) + (N / 2)( C )
f(N) = C * (( N ^ 2 / 2 ) - (N ^ 2 / 4) + (N / 2)) + (N / 2)( C )
f(N) = C * ( N ^ 2 / 4 ) + C * (N / 2) + C * (N / 2)
f(N) = C * ( N ^ 2 / 4 ) + 2 * C * (N / 2)
f(N) = C * ( N ^ 2 / 4 ) + C * N
f(N) = C * 1/4 * N ^ 2 + C * N
BigOh是：
O(N²)
大O给出算法的时间复杂度的上限。 它通常与处理数据集（列表）结合使用，但可用于别处。
关于C代码如何使用的几个例子。
假设我们有n个元素的数组
int array[n];
如果我们想要访问数组的第一个元素，这将是O（1），因为它与数组的大小无关，它总是需要相同的时间来获得第一个项目。
x = array[0];
如果我们想在列表中找到一个数字：
for(int i = 0; i < n; i++){
if(array[i] == numToFind){ return i; }
}
这将是O（n），因为我们至多需要查看整个列表才能找到我们的号码。 大O仍然是O（n），尽管我们可能会发现我们的数字是第一次尝试并且一次遍历循环，因为Big-O描述了算法的上界（欧米茄用于下界，θ用于紧界） 。
当我们得到嵌套循环时：
for(int i = 0; i < n; i++){
for(int j = i; j < n; j++){
array[j] += 2;
}
}
这是O（n ^ 2），因为对于外部循环（O（n））的每次通过，我们必须再次遍历整个列表，所以n的乘法使我们与n平方。
这几乎不能抓到表面，但当分析更复杂的算法时，涉及证明的复杂数学就会发挥作用。 至少希望这会让你熟悉基本知识。
在知道如何确定特定问题的大时间是有用的，了解一些常规情况可以帮助您在算法中做出决定。
以下是一些最常见的情况，从http://en.wikipedia.org/wiki/Big_O_notation#Orders_of_common_functions中解除：
O（1） - 确定数字是偶数还是奇数; 使用恒定大小的查找表或散列表
O（logn） - 使用二分搜索查找排序数组中的项目
O（n） - 在未排序列表中查找项目; 增加两个n位数字
O（n2） - 用一个简单的算法乘以两个n位数字; 添加两个n×n矩阵; 冒泡排序或插入排序
O（n3） - 用简单的算法乘以两个n×n矩阵
O（cn） - 使用动态规划查找旅行商问题的（确切）解决方案; 使用蛮力确定两个逻辑语句是否相同
O（n！） - 通过蛮力搜索解决旅行商问题
O（nn） - 通常用来代替O（n！）来导出更简单的公式以实现渐近复杂性
链接地址: http://www.djcxy.com/p/1025.html