ds_c01 算法性能分析.md

5. 算法性能评价指标

Big O notation is a mathematical notation that describes the limiting behavior of a function when the argument tends towards a particular value or infinity.

In computer science, big O notation is used to classify algorithms according to how their run time or space requirements grow as the input size grows.

来自：wiki: big_O_notation

在计算机中，大 O 表示法常作为衡量算法的运行时间或所需内存空间随输入规模增长而发生变化的度量；

5.1 时间复杂度的计算（大 O 表示法）

用来衡量运行时间时，它为算法在最坏情况下运行时间的上界，即为任意规模的数据的运行时间的上界。

例如，插入排序，在数据有序的情况下，时间复杂度为 O(n)；如果数据是逆序的，那么插入排序的时间复杂度就是 O(n^2)；对所有数据来说，最差情况下的时间复杂度为 O(n^2)，所以称插入排序的时间复杂度为 O(n^2)。

以上结论和例子据说来自《算法导论》

常用的计算方法：

• 频度计算法：
  • 假设所有的语句执行的时间相同，计算所有语句的频度 T(n)；
  • T(n) 的最高次项即为 O(f(n))（不需要保留最高次项的常数）；
• 一般的计算步骤：
  • 找到所有语句中执行次数最多的那条语句作为基本语句；
  • 计算基本语句执行次数的数量级；
  • 取其数量级用大 O 表示即可；例如 O(n)、O(logn)等等；
• 含有递归的时间复杂度的分析：
  • 每一次调用函数的时间复杂度 * 函数的调用次数

    int fact(int n) {
        if (n <= 1) return 1;
        return n * fact(n - 1);
    }
    

    在上述代码中，每次调用函数的时间复杂度为 O(1)，调用次数为 O(n)，所以总的时间复杂度为 O(n)；
• 一些特殊的技巧：写出第 i 次循环后，循环变量的值；

  int func(int n) {
      int i = 0, sum = 0;
      while (sum < n) sum += ++i;
      return i;
  }
  
  /***时间复杂度分析
  1: sum = 1
  2: sum = 1 + 2
  3: sum = 1 + 2 + 3
  ...
  i: sum = i(1+i)/2 < n
  因为 sum 要大于等于 n 才退出循环，
  所以 i 的上界可以为 sqrt(n)
  ***/
  
  x = 0;
  while (n >= (x+1)*(x+)) x+=1;
  
  /***时间复杂度分析
  i: (i+1)*(i+1) <= n
  O(sqrt(n)) 
  ***/
  

• 加法法则，乘法法则；

5.2 空间复杂度的计算（大 O 表示法）

• 非递归问题的空间复杂度分析

  int j = 0;
  int k = 0;
  for (int i = 0; i < n; i ++) {
    j ++;
    k ++;
  }
  
  /*** 空间复杂度分析
  开辟了 i、j、k 三个数据空间，所以空间复杂度为 O(1)
  ***/
  
  int *a = new int(n);
  for (int i = 0; i < n; i ++) a[i] = i;
  
  /*** 空间复杂度分析
  数组空间随着 n 的增大而增大，且保持线性的速度，
  所以空间复杂度为 O(n)
  ***/
  

• 递归问题的空间复杂度分析

  int fib(int n) {
    if (n <= 1) return n;
    else return fib(n - 1) + fib(n - 2);
  }
  

  

  递归问题的空间复杂度 = 每一层的空间复杂度 * 递归深度；

  数据结构一般只考虑单个进程单个线程的情况，所以上述最大的所需的栈空间为每一层的空间复杂度 * 递归深度

  int test(int n) {
    if (n <= 1) return 1;
    test(n/2);
  }
  
  /*** 空间复杂度分析
  每一层的空间复杂度为 O(1)，递归深度为 O(logn)
  所以空间复杂度为 O(logn)
  ***/
  

5.3 算法题：判断素数、最大连续子序列问题

bool isPrime(int n) {
    bool prime = true;
    for (int i = 1; i < n; i ++)
        if (n % i == 0)
            prime = false;
    
    return prime;
}