我将尽我所能在这里用简单的术语来解释它，但请注意，这个主题需要我的学生几个月才能最终掌握。您可以在 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，我们需要对函数进行渐近分析。大致是这样完成的：

1. 带走所有的常数C。
2. 从f()得到它的多项式standard form。
3. 将多项式的各项除以增长率并对其进行排序。
4. 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)( ... )

第二 句更加棘手，因为它取决于 的值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向上时，内部求和以负数结束！这是不可能的，也是错误的。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 执行复杂度恒定。

现在可以使用一些恒等规则来简化求和：

1. 求和（w 从 1 到 N）( C ) = N * C
2. 求和(w 从 1 到 N)( A (+/-) B ) = 求和(w 从 1 到 N)( A ) (+/-) 求和(w 从 1 到 N)( B )
3. Summation(w from 1 to N)( w * C ) = C * Summation(w from 1 to N)( w ) (C 是一个常数，独立于w)
4. 求和（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虏)