常见排序算法的时间复杂度

事后统计法

测试结果非常依赖测试环境
测试结果受数据规模的影响很大

大 O 复杂度表示法

大O符号

大O符号（英语：Big O notation），又称为渐进符号，是用于描述函数渐近行为的数学符号。更确切地说，它是用另一个（通常更简单的）函数来描述一个函数数量级的渐近上界。

大O符号是由德国数论学家保罗·巴赫曼在其1892年的著作《解析数论》（Analytische Zahlentheorie）首先引入的。而这个记号则是在另一位德国数论学家艾德蒙·朗道的著作中才推广的，因此它有时又称为朗道符号（Landau symbols）。代表“order of ...”（……阶）的大O，最初是一个大写希腊字母“Ο”（omicron），现今用的是大写拉丁字母“O”。

大 O 时间复杂度

大 O 时间复杂度实际上并不具体表示代码真正的执行时间，而是表示代码执行时间随数据规模增长的变化趋势，所以，也叫作渐进时间复杂度，简称时间复杂度。

怎么计算时间复杂度

Tn = O(f(n))
而公式中的低阶、常量、系数三部分并不左右增长趋势，所以都可以忽略。我们只需要记录一个最大量级就可以了

只关注循环执行次数最多的一段代码

加法法则：总复杂度等于量级最大的那段代码的复杂度

int cal(int n) {
   int sum_1 = 0;
   int p = 1;
   for (; p < 100; ++p) {
     sum_1 = sum_1 + p;
   }

   int sum_2 = 0;
   int q = 1;
   for (; q < n; ++q) {
     sum_2 = sum_2 + q;
   }
 
   int sum_3 = 0;
   int i = 1;
   int j = 1;
   for (; i <= n; ++i) {
     j = 1; 
     for (; j <= n; ++j) {
       sum_3 = sum_3 +  i * j;
     }
   }
 
   return sum_1 + sum_2 + sum_3;
 }

乘法法则：嵌套代码的复杂度等于嵌套内外代码复杂度的乘积

int cal(int n) {
   int ret = 0; 
   int i = 1;
   for (; i < n; ++i) {
     ret = ret + f(i);
   } 
 } 
 
 int f(int n) {
  int sum = 0;
  int i = 1;
  for (; i < n; ++i) {
    sum = sum + i;
  } 
  return sum;
 }

常见时间复杂度实例分析

O(1)

 int i = 8;
 int j = 6;
 int sum = i + j;

O(logn)、O(nlogn)

 i=1;
 while (i <= n)  {
   i = i * 2;
 }

 i=1;
 while (i <= n)  {
   i = i * 3;
 }

O(m+n)、O(m*n)

int cal(int m, int n) {
  int sum_1 = 0;
  int i = 1;
  for (; i < m; ++i) {
    sum_1 = sum_1 + i;
  }

  int sum_2 = 0;
  int j = 1;
  for (; j < n; ++j) {
    sum_2 = sum_2 + j;
  }

  return sum_1 + sum_2;
}

最好、最坏、平均、均摊时间复杂度

同一段代码在不同情况下时间复杂度会出现量级差异，为了更全面，更准确的描述代码的时间复杂度，所以引入这4个概念。

最好：最理想的情况下
最坏：在最糟糕的情况下
平均：加权平均时间复杂度
均摊：一种特殊的，通过摊还分析得到的平均时间复杂度

时间复杂度表示

O：big-O————上界
Ω：big-Omega—–下界（很少用）
Θ：big-Theta——-确界

示例：find

// n 表示数组 array 的长度
int find(int[] array, int n, int x) {
  int i = 0;
  int pos = -1;
  for (; i < n; ++i) {
    if (array[i] == x) {
       pos = i;
       break;
    }
  }
  return pos;
}

最好：Ω(1)
最坏：O(n)
平均：O(n)

摊还分析法：将较高时间复杂度那次操作的耗时，平摊到其他那些时间复杂度比较低的操作上。适用于低级别和高级别复杂度出现具有时序规律。均摊结果一般都等于低级别复杂度。

示例：insert

// array 表示一个长度为 n 的数组
// 代码中的 array.length 就等于 n
int[] array = new int[n];
int count = 0;
void insert(int val) {
   if (count == array.length) {
      int sum = 0;
      for (int i = 0; i < array.length; ++i) {
         sum = sum + array[i];
      }
      array[0] = sum;
      count = 1;
   }

   array[count] = val;
   ++count;
}

最好：Ω(1)
最坏：O(n)
平均：O(1)

能够应用均摊时间复杂度分析的场合，一般均摊时间复杂度就等于最好情况时间复杂度

常见排序算法的时间复杂度

排序算法	最佳时间复杂度	平均时间复杂度	最坏时间复杂度	稳定性
选择排序	O(N^2)	O(N^2)	O(N^2)	不稳定
插入排序	O(N)	O(N^2)	O(N^2)	稳定
冒泡排序	O(N)	O(N^2)	O(N^2)	稳定
希尔排序	O(N)	O(NlogN)	O(N^S)（1<S<2）	不稳定
快速排序	O(NlogN)	O(NlogN)	O(N^2)	不稳定
堆排序	O(NlogN)	O(NlogN)	O(NlogN)	不稳定
归并排序	O(NlogN)	O(NlogN)	O(NlogN)	稳定

空间复杂度

渐进空间复杂度，表示算法的存储空间与数据规模之间的增长关系。
是对一个算法在运行过程中临时占用存储空间大小的量度

func TestRoom(t *testing.T) {
    var n int = 10000
    var list = new([1000]int)
    for i := 0; i < n; i++ {
        list[i%1000] = i
        fmt.Println(i%1000, i)
    }
}

//?
func TestRoom2(t *testing.T) {
    var n int = 10000
    var list []int
    for i := 0; i < n; i++ {
        list = append(list, i)
    }
}