算法分析 | 大O分析

banq
我们可以使用大 O 表示法来表达算法的复杂性。对于大小为 N 的问题：
  • 恒定时间函数/方法是“阶数 1”：O(1)
  • 线性时间函数/方法是“N 阶”：O(N)
  • 二次时间函数/方法是“N 次方”：O(N 2 )

定义设 g 和 f 是自然数集到自身的函数。如果存在一个常数 c > 0 和一个自然数 n0，使得对于所有 n ≥ n0，f(n) ≤ cg(n)，则称函数 f 为 O(g)（读作 g 的 big-oh）。

注意：O(g) 是一个集合！

滥用符号：f = O(g) 并不意味着 f ∈ O(g)。

Big-O 渐近符号为我们提供了上界思想，数学描述如下： 

如果存在一个正整数 n0 和一个正常数 c，使得 f(n)≤c.g(n) ∀ n≥n0 则 f(n) = O(g(n)

Big-O 运行分析的一般步骤如下：  

  • 弄清输入是什么，n 代表什么。
  • 用 n 表示算法执行的最大操作数。
  • 除去所有最高阶项。
  • 去除所有常数因子。

Big-O 符号分析的一些有用特性如下：

 常数乘法：

  • 如果 f(n) = c.g(n)，那么 O(f(n)) = O(g(n))；其中 c 是一个非零常数。
 多项式函数：
  • 若 f(n) = a0 + a1.n + a2.n2 + -- + am.nm，则 O(f(n)) = O(nm)。
 求和函数：
  • 如果 f(n) = f1(n) + f2(n) + -- + fm(n) 且 fi(n)≤fi+1(n) ∀ i=1, 2, --, m、
  • 则 O(f(n)) = O(max(f1(n), f2(n), --, fm(n))).
 对数函数：
  • 如果 f(n) = logan，g(n)=logbn，则 O(f(n))=O(g(n))
  • 所有对数函数的增长方式都与 Big-O 相同。

基本上，这种渐近符号用于从理论上衡量和比较算法的最坏情况。对于任何算法，只要我们能正确识别与 n（输入大小）相关的运算，Big-O 分析就会变得简单明了。
算法的运行时分析

在一般情况下，我们主要测量和比较算法最坏情况下的理论运行时间复杂性，以进行性能分析。

任何算法的最快运行时间都是 O(1)，通常称为恒定运行时间。在这种情况下，无论输入大小如何，算法的执行时间总是相同的。这是算法的理想运行时间，但很少能实现。

在实际情况中，算法的性能（运行时间）取决于 n，即输入的大小或每个输入项所需的操作次数。

按照性能（运行时间复杂度）从优到劣，算法可分为以下几类：

对数算法 - O(logn)

  • 运行时间与 n 成对数增长。
 线性算法 - O(n)
  • 运行时间与 n 成正比增长。
 超线性算法 - O(nlogn)
  • 运行时间与 n 成正比增长。
 多项式算法 - O(nc)
  • 运行时间的增长速度比前面所有基于 n 的算法都要快。
 指数算法 - O(cn)
  • 运行时间比基于 n 的多项式算法增长更快。
 阶乘算法 - O(n!)
  • 运行时间增长最快，甚至在 n 值较小的情况下也很快无法使用。
  • 运行时间增长最快，甚至对于较小的 n 值也很快变得不可用。

运行时分析算法示例：
以下是所有这些类型算法（在最坏情况下）的一些示例：

  •  对数算法 - O(logn) - 二进制搜索。
  •  线性算法 - O(n) - 线性搜索。
  •  超线性算法 - O(nlogn) - 堆排序、合并排序。
  •  多项式算法 - O(n^c) - 斯特拉森矩阵乘法、泡排序、选择排序、插入排序、桶排序。
  •  指数算法 - O(c^n) - 河内塔。
  •  因子算法--O(n!) - 小数的行列式展开、旅行推销员问题的蛮力搜索算法。

运行时间分析的数学实例：
随着 n（输入大小）的增大，不同等级算法的性能（运行时间）会迅速分离。让我们来看一个数学例子：

If n = 10,                  If n=20,
    log(10) = 1;                log(20) = 2.996;
    10 = 10;                    20 = 20;
    10log(10)=10;               20log(20)=59.9;
    102=100;                    202=400;
    210=1024;                    220=1048576;
    10!=3628800;                20!=2.432902e+1818;

算法的内存足迹分析

要对算法进行性能分析，运行时间测量不仅是相关指标，我们还需要考虑程序的内存使用量。这就是算法的内存足迹，简称空间复杂度。
在这里，我们还需要测量和比较算法最坏情况下的理论空间复杂度，以便进行性能分析。
这基本上取决于以下两个主要方面：

  • 首先，程序的实现负责内存的使用。例如，我们可以假设递归实现总是比特定问题的相应迭代实现预留更多内存。
  • 另一个是 n，即输入大小或每个项目所需的存储量。例如，输入量大的简单算法会比输入量小的复杂算法消耗更多内存。

内存足迹分析算法实例：根据最坏情况，从最佳性能（空间复杂度）到最差性能（空间复杂度）的算法示例分类如下：  

  • 理想算法 - O(1) - 线性搜索、二进制搜索、
  •     气泡排序、选择排序、插入排序、堆排序、壳排序。
  •  对数算法 - O(log n) - 合并排序。
  •  线性算法 - O(n) - 快速排序。
  •  子线性算法 - O(n+k) - Radix 排序。

时空权衡和效率
通常需要在最佳内存使用和运行时性能之间进行权衡。 一般来说，对于一个算法来说，空间效率和时间效率到达两个相对的两端，并且它们之间的每个点都有一定的时间和空间效率。因此，时间效率越高，空间效率就越低，反之亦然。 例如，归并排序算法非常快，但需要大量空间来执行操作。另一方面，冒泡排序非常慢，但需要的空间最小。 

在本主题结束时，我们可以得出结论，找到一种运行时间较短且对内存空间要求较低的算法，可以对算法的性能产生巨大影响。

// 查找单个 for 循环时间复杂性的 Java 程序

import java.io.*;

class GFG {
    public static void main(String[] args)
    {
        // declare variable
        int a = 0, b = 0;
        // declare size
        int N = 5, M = 5;
        //这个循环运行 N 次
        for (int i = 0; i < N; i++)
            a += 5;
        //此循环运行 M 次
        for (int i = 0; i < M; i++)
            b += 10;
        // 打印 a 和 b 的值
        System.out.println(a + " " + b);
    }
}


输出
25 50

解释： 第一个循环运行N次，而第二个循环运行M次。计算需要O(1) 次。因此，将它们相加，时间复杂度将为 O ( N + M + 1) = O( N + M) 。
时间复杂度：O(N + M) 或 O(M) 或 O(N) [as, M=N]