算法初步（julyedu网课整理）

1

O(1)

基本运算

O(logn)

二分查找分治类问题基本上都有log

O(n)

线性查找

O(n²)

冒泡排序；选择排序

O(n的3次方)

Floyd最短路；普通矩阵乘法

O(nlogn)

归并排序和快速排序的期望复杂度；
基于比较排序的算法下界
原因：a1 a2 …… an 等n个数共有n！次种分布可能
比较一次 ai > aj 就筛选出来一半的结果 n！/ 2
比较第二次 ai > aj 就筛选出来一半结果的一半 n！/ 4 = n！/ 2 ²
做k次比较 n！/ 2的k次方
所以要经过多少次比较才能得到最后的排序结果？
n！/ 2的k次方 = 1
n！ = 2的k次方
两边同时以2为底 log
log(n！) = k
因为log(n！) < log(n的n次方)
所以 k ≈ log(n的n次方) ≈ nlogn 下限最坏是nlogn

O(2的n次方)

暴力枚举所有子集

2

数组

数据在内存中连续存储：数组；非连续存储：链表、树；
vector(C++) 读写速率都是O(1)
当数组空间满了，vector会自动开辟一个两倍空间，丢弃原来的空间，将原始数据copy过来，有k个数则时间复杂度O(k)

3

算法优化的时候会从最内层循环开始，因为最内层会被一直循环执行
ex:一个数组中，某一子集的和最大
ans = -2147483647 作为判断的下界
int最小值 -2147483648 最大值2147483647
暴力枚举：三重循环

for i ← 1 to n
	for j ← i to n  
		sum ← a[i] + ... + a[j]
		ans ← max(ans,sum)
时间复杂度O(n的3次方) 附加空间复杂度O(1)

优化枚举：两重循环
a[2] + a[3]
a[2] + a[3] + a[4]
=> 不需要挨个加一遍，只需要把之前的结果保存再加后面的那一个数即可

for i ← 1 to n
		sum ← 0
	for j ← i to n  
    	sum ← sum + a[j]
    	ans ← max(ans,sum)
时间复杂度O(n²) 附加空间复杂度O(1)

贪心算法：一重循环

sum ← 0; ans ← 0
for i ← 1 to n
	sum = sum + a[i]
	ans ← max(ans,sum)
	if(sum < 0)
		sum ← 0
时间复杂度O(n) 附加空间复杂度O(1)

if(sum < 0) sum ← 0 这部分是代码最终优化之后的结果，但是直接看的话不容易理解

再优化：求最大值问题转化成求最小值问题
问题是求 max(a[i]…a[j])
假设 s[i] = a[0] + … + a[i]
那么问题就转化成 max(s[j] - s[i - 1])
对数组中的每一个j来说，s[j]是固定的，循环累加得到
那么问题就转化成 max(P - s[i - 1])，找到min(s[i - 1])

public int maxSubArray(int[] nums) {
    int n = nums.length;
    if(n == 0)
        return 0;
    int si = 0; 
    int sj = 0; 
    int minSi = 0; 
    int ans = Integer.MIN_VALUE;
    for(int j = 0; j < n; ++j){
	    sj += nums[j];
	    if(si < minSi)
		    minSi = si;
	    if(sj - minSi > ans)
		    ans = sj - minSi;
	    si += nums[j];
    }
    return ans;
}

ex：[-2,1,-3,4,-1,2,1,-5,4]

sj	minSi	ans	si	j
-2	0	-2	-2	0
-1	-2	1	-1	1
-4	-2	1	-4	2
0	-4	4	0	3
-1	-4	4	-1	4
1	-4	5	1	5
2	-4	5	2	6

sj不断累积
minSi取[0]…[j]中最小的那一个值
ans取sj - minSi中最大的那个一个值

优化：
sj += nums[j]
可以直接删掉，sj = si +nums[j]

public int maxSubArray(int[] nums) {
    int n = nums.length;
    if(n == 0)
        return 0;
    int si = 0; 
    int minSi = 0; 
    int ans = Integer.MIN_VALUE;
    for(int j = 0; j < n; ++j){
	    if(si < minSi)
		    minSi = si;
	    if(si + nums[j] - minSi > ans)
		    ans = si + nums[j] - minSi;
	    si += nums[j];
    }
    return ans;
}

之后 if(si < minSi) 可以表示为 if(si - minSi < 0)
新建一个变量 sum 用来表示 si - minSi 进行变量替换,初始值为0
同时因为此时已经没有 minSi 了，所以对 si 的增量就相当于对 sum 的增量，所以 si += nums[j]就可以表示为 sum += nums[j]

public int maxSubArray(int[] nums) {
    int n = nums.length;
    if(n == 0)
        return 0;
	int sum = 0;
    int ans = Integer.MIN_VALUE;
    for(int j = 0; j < n; ++j){
	    if(sum < 0)
		    sum = 0;
	    if(sum + nums[j] > ans)
		    ans = sum + nums[j];
	    sum += nums[j];
    }
    return ans;
}

此时的代码和贪心法的一重循环是一致的