algorithm - 大O，您如何计算/近似？

Question

大多数拥有计算机科学学位的人肯定知道什么是Big O stands for。
它有助于我们衡量一个算法的实际效率，如果您知道在what category the problem you are trying to solve lays in中，您可以找出是否仍然有可能挤出这一点额外的性能
但我很好奇，你如何计算或近似你的算法的复杂性？
但正如他们所说，不要做得太过分，premature optimization is the root of all evil，没有正当理由的优化也应该得到这个名字。

Answer 1

我会尽我所能用简单的术语来解释，但请注意，这个话题需要我的学生几个月的时间才能最终掌握。您可以在Data Structures and Algorithms in Java一书的第2章中找到更多信息。
没有mechanical procedure可以用来获取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
}

此函数返回数组中所有元素的和，我们要创建一个公式来计算该函数的 computational complexity：

Number_Of_Steps = f(N)

所以我们有一个计算步数的函数。函数的输入是要处理的结构的大小。这意味着此函数的调用方式如下：

Number_Of_Steps = f(data.length)

参数 f(N)取 N值现在我们需要函数 data.length的实际定义。这是从源代码中完成的，在源代码中，每一个有趣的行的编号从1到4。
有很多方法可以计算出BigOh从这一点出发，我们假设每个不依赖于输入数据大小的句子都需要一个常数 f()的计算步骤。
我们将添加函数的各个步骤，并且局部变量声明和返回语句都不取决于 C数组的大小。
这意味着第1行和第4行各执行c个步骤，函数有点像这样：

f(N) = C + ??? + C

下一部分是定义 data语句的值。请记住，我们正在计算计算步骤的数量，这意味着 for语句的主体将被执行 for次。这与添加 N， C次相同：

f(N) = C + (C + C + ... + C) + C = C + N * C + C

没有计算 N主体执行多少次的机械规则，您需要通过查看代码的作用来计算它为了简化计算，我们忽略了 for语句的变量初始化、条件和增量部分。
为了得到实际的bigoh，我们需要函数的 Asymptotic analysis。大致如下：
去掉所有常数 for。
从 C中获取其 f()中的 polynomium。
把多项式的项分开，按增长率排序。
当 standard form接近 N时，让它变大。
我们的 infinity有两个术语：

f(N) = 2 * C * N ^ 0 + 1 * C * N ^ 1

去掉所有 f()常数和多余部分：

f(N) = 1 + N ^ 1

因为最后一个项是当 C接近无穷大时变大的项（想想 limits），这就是bigoh参数， f()函数有一个bigoh：

O(N)

有一些技巧可以解决一些棘手的问题：尽可能使用 summations。
例如，可以使用求和来轻松解决此代码：

for (i = 0; i < 2*n; i += 2) {  // 1
    for (j=n; j > i; j--) {     // 2
        foo();                  // 3
    }
}

首先需要询问的是 sum()的执行顺序。虽然通常是 foo()，但您需要向您的教授询问这方面的情况 O(1)表示（几乎，大部分）常数 O(1)，与大小无关。
第一个句子的 C语句很棘手。当索引结束于 N时，增量由两个完成。这意味着第一个 for只执行 2 * N步，我们需要将计数除以2。

f(N) = Summation(i from 1 to 2 * N / 2)( ... ) = 
     = Summation(i from 1 to N)( ... )

第二个句子更加复杂，因为它取决于 for的值。看一看：索引i的值是：0，2，4，6，8，…，2*n，第二个 N执行：n乘以第一个，n-2，第二个，n-4，第三个…直到n/2阶段，第二个 i永远不会执行。
在公式上，这意味着：

f(N) = Summation(i from 1 to N)( Summation(j = ???)(  ) )

同样，我们正在计算步数。根据定义，每次求和都应该从一开始，到大于或等于一的数字结束。

f(N) = Summation(i from 1 to N)( Summation(j = 1 to (N - (i - 1) * 2)( C ) )

（我们假设 for是 for并采取 foo()步骤。）
这里有一个问题：当 O(1)向上取值时，内部求和以负数结束！这是不可能的，也是错误的我们需要把总和一分为二，因为这是 C的关键时刻。

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 + 1不会被执行，并且我们假设它的主体上存在常数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是一个常数，与 i无关）
求和（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

最大的问题是：

O(N²)