算法与数据结构
时间复杂度
数组结构:常数复杂度:+ - * / 位运算(与数据量无关)
链表结构:遍历->O(n)
选择排序
aN^2+bN+c -> O(N^2): 只取最高阶项,且忽略系数 (设上限)
1 | selectionsort(int[] arr){ |
先看时间复杂度指标,时间复杂度一致时,需实际跑代码比较优劣。
额外空间复杂度O(1)
冒泡排序: 大的数依次向右移动 O(N^2)
1 | bubblesort(int[] arr) |
异或运算:对0 1两个数进行操作;相同为0;不同为1; (或二进制的无进位相加)
- 0 ^ N = N ; N ^ N = 0
- 满足交换律和结合律 a^b=b^a ; (a^b)^c = a^(b^c)
- 同一组数据,异或结果与顺序无关。
Q1:在一个数组中,已知只有一种数出现奇数次,其他数出现偶数次,如何找到?
Q2:在一个数组中,已知只有两种数出现奇数次,其他数出现偶数次,如何找到?
要求时间复杂度为O(N)
A1: int eor=0 ; 提取数组的所有数,进行异或:arr[0]^arr[1]^……arr[n]=结果
A2: 先所有数组进行异或 eor=a^b,接着依次取出一个数与该结果异或,得到结果。
位运算操作(二进制):一个数取反加1,可以都到最右侧的数。
插入排序
0-0有序->0-1有序->0-2有序…………
4,5,6,7,3,2,1 -> O(N^2)
1,2,3,4,5,6,7 -> 0(N)
时间复杂度由算法最差情况的表现决定。
1 | insertsort(int[] arr) |
二分法的详解与扩展
- 在一个有序数组中,找到某个数的存在
(1)遍历 O(N)
(2)二分 O(log2(N))
- 在一个有序数组中,找到某个数的存在
- 在一个有序数组中,找到>=某个数最左侧的位置
ex: 1 2 2 2 2 3 3 3 3 4 4 4 4 4 4 4
- 在一个有序数组中,找到>=某个数最左侧的位置
- 局部最小值问题
在一个无序数组中,任何两个相邻的数不相等,求一个局部最小的过程 在时间复杂度上好于O(N)
A: 1 3 5 7 4 9 6 3 2
先看0位置和n-1位置是否存在局部最小,若不,则中间必有局部最小。
接下来继续比较运用二分法。
- 局部最小值问题
对数器
优秀方法(想测试的):考虑时间复杂度,追求优解
普通方法:不考虑时间复杂度,只考虑解决问题
用随机样本产生器,对两种方法运行一遍,结果一样,则说明优秀方法正确。
剖析递归行为及其时间复杂度的估算
求一个数组的最大值
1 | process (int[] arr ,int L , int R) |
- master公式: T(N)=a*T(N/b)+O(N^d)
T(N):母问题的数据量为N级别 T(N/b):子问题的规模都是N/b a:子问题的调用次数 O(N^d):除去子问题外剩下过程的时间复杂度
- logb(a)<d -> O(N^d)
- logb(a)>d -> O(N^logb(a))
- logb(a)==d -> O(N^d*logN)
归并排序
中点切一半,左右各自排好序,最后组合
1 | void mergeSort(int[] arr) |
时间复杂度: T(N) = 2 * T(N/2) + O(N) —> O(N*logN)
额外空间复杂度:O(N)
- 扩展问题:小和问题和逆序对问题
小和问题:在一个数组中,每一个数左边比当前数小的数累加起来,叫做这个数组的小和,求一个数组的小和
ex: 1 3 4 2 5 -> 0 + 1 + 1 + 3 + 1 + 1 + 3 + 4 + 2 = 16
另一种思想: 左边有多少个数比该数大 41+23+14+12=16逆序对问题:在一个数组中,左边的数如果比右边的数大,则这两个数构成一个逆序对,打印所有的逆序对。
b