我将尽力在这里用简单的术语解释它，但请注意，这个主题需要我的学生几个月的时间才能最终掌握。您可以在第 2 章中找到更多信息Java 中的数据结构和算法 book.
没有机械程序可以用来获得 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 array.
这意味着第 1 行和第 4 行各需要 C 个步骤，函数有点像这样：
f(N) = C + ??? + C
下一部分是定义的值for陈述。请记住，我们正在计算计算步骤的数量，这意味着for语句被执行N次。这与添加相同C, N times:
f(N) = C + (C + C + ... + C) + C = C + N * C + C
没有机械规则来计算身体的次数for被执行后，你需要通过查看代码做了什么来计算它。为了简化计算，我们忽略变量初始化、条件和增量部分for陈述。
为了获得真正的 BigOh，我们需要渐近分析的函数。这大致是这样完成的：
- 去掉所有常数
C.
- From
f()得到多项式 in its standard form.
- 将多项式的项相除并按增长率排序。
- 保留长大的那个
N方法infinity.
Our f()有两个术语：
f(N) = 2 * C * N ^ 0 + 1 * C * N ^ 1
带走所有的C常量和冗余部分：
f(N) = 1 + N ^ 1
由于最后一项在以下情况下会变得更大：f()接近无穷大（思考limits）这是 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.
The for关于第一句话的陈述很棘手。虽然索引结束于2 * N，增量为 2。这意味着第一个for仅被执行N步骤，我们需要将计数除以二。
f(N) = Summation(i from 1 to 2 * N / 2)( ... ) =
= Summation(i from 1 to N)( ... )
句子编号two甚至更棘手，因为它取决于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() is O(1)并采取C steps.)
我们这里有一个问题：当i取值N / 2 + 1向上，内部求和以负数结束！这是不可能的，也是错误的。我们需要将求和一分为二，作为此刻的关键点i takes 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 * N
f(N) = C * 1/4 * N ^ 2 + C * N
BigOh 是：
O(N²)
