事后统计法
测试结果非常依赖测试环境
测试结果受数据规模的影响很大
大 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;
}
常见时间复杂度实例分析
image.png
image.png
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)
image.png
摊还分析法：将较高时间复杂度那次操作的耗时，平摊到其他那些时间复杂度比较低的操作上。适用于低级别和高级别复杂度出现具有时序规律。均摊结果一般都等于低级别复杂度。
示例：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)
}
}
引用：
https://blog.csdn.net/qq_35556064/article/details/82888717
https://blog.csdn.net/Michael__Jack/article/details/71075459
极客时间: https://time.geekbang.org/column/article/41149
https://zh.wikipedia.org/wiki/%E5%A4%A7O%E7%AC%A6%E5%8F%B7
网友评论