1.大 O 时间复杂度表示法

1.0 常见时间复杂度

渐进时间复杂度

• 加法准则:总复杂度等于量级最大的那段代码的复杂度
• 乘法准则:嵌套代码的复杂度等于嵌套内外代码复杂度乘积

从低阶到高阶:O(1)、O(logn)、O(n)、O(nlogn)、O(n2)

1.1 O(log n),O(n log n)

 i=1;while (i <= n)  {i = i * 2;}
// 时间复杂度分析: 2的x次方 = n, x = log2(n),即O(log n)
// 外面在套一个 for循环(n次),此时时间复杂度就是 O(nlogn)

1.2 O(m+n),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;
}

2. 空间复杂度分析

渐进空间复杂度.

// 空间复杂度 O(n)
void print(int n) {int i = 0;  // 常量介,忽略int[] a = new int[n]; //nfor (i; i <n; ++i) {a[i] = i * i;}for (i = n-1; i >= 0; --i) {print out a[i]}
}

3. 最好,最坏,平均,均摊复杂度

3.1 平均时间复杂度(只有在特殊情况下才用到)

// 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;
}
// 最好: 第一个就找到了 O(1)
// 最坏: 最后一个才找到 O(n)
// 平均: O(n)

平均时间复杂度分析

​ 查找变量 x的位置,在数组 0~n-1的位置下或者不在数组中,共n+1 种情况.把每种情况需要遍历的元素个数累加起来在除以 n+1,就是平均值:

​ (1+2+3+…+n-1+n+n)/(n+1) = n(n+3)/2(n+1) .去掉常数低阶系数等,得到 O(n)

实际情况,我们只要使用一个时间复杂度就可以满足需求了.

3.2 均摊时间复杂度

 // array表示一个长度为n的数组// 代码中的array.length就等于nint[] 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;}
/*
实现的功能就是: 往数组里插入数据,数组没满,直接插入,满了,计算数组的和,
将和放在数组的第0个位置,然后将后面的清空.(这里的清空不是实际的清空,就是指针移到了1的位置,即清空了后面的元素)
最好:O(1) 数组未满
最坏:O(n) 数组满了
平均:O(1)
*/

平均时间复杂度计算:

• 插入分为 n+1 种情况,首先数组未满,n种+数组满了的一种情况.

• 每种情况的概率是 1/(n+1)

• 加权平均计算方法:

  

均摊时间复杂度

• 这个例子里的 n-1次 O(1) 然后跟着 一个 O(n).
• 将 一次O(n)的时间复杂度均摊到 n- 1 次耗时少的操作上
• 结果就是 O(1)

4.小练习

// 全局变量，大小为10的数组array，长度len，下标i。
int array[] = new int[10]; 
int len = 10;
int i = 0;// 往数组中添加一个元素
void add(int element) {if (i >= len) { // 数组空间不够了// 重新申请一个2倍大小的数组空间int new_array[] = new int[len*2];// 把原来array数组中的数据依次copy到new_arrayfor (int j = 0; j < len; ++j) {new_array[j] = array[j];}// new_array复制给array，array现在大小就是2倍len了array = new_array;len = 2 * len;}// 将element放到下标为i的位置，下标i加一array[i] = element;++i;
}

add()时间复杂度:

• 最好:O(1)
• 最坏:O(n)
• 平均:O(1)