我会尽力在这里简单地解释它，但要注意，这个主题需要我的学生花几个月的时间才能最终掌握。您可以[在《Java中的[数据结构和算法》第二章中找到更多信息。
没有可用于获取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数量的计算步骤。
我们将添加函数的各个步骤，并且局部变量声明和return语句都不依赖于
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()
获得polynomium它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步骤，我们需要将计数除以二。
f(N) = Summation(i from 1 to 2 * N / 2)( ... ) = = Summation(i from 1 to N)( ... )
句号码 2 是更加棘手，因为它取决于价值
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的数字结束。
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向上取整时，内部求和运算将以负数结束！那是不可能的，也是错误的。我们需要将求和一分为二，这是当前
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从1到N）（C）= N * C
- 求和（w从1到N）（A（+/-）B）=求和（w从1到N）（A）（+/-）求和（w从1到N）（B）
- 求和（w从1到N）（w * C）= C *求和（w从1到N）（w）（C是一个常数，独立于
w
） - 求和（w从1到N）（w）=（N *（N + 1））/ 2
应用一些代数：
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 * Nf(N) = C * 1/4 * N ^ 2 + C * N
BigOh是：
O(N²)
