算法分析
非极端元素+冒泡排序
算法分析：
通过挖掘算法中的不变性、单调性，进而证明正确性是算法分析的重要技巧。
迭代与递归
减而治之 (decrease and conquer)
求解一个大规模问题，可以将其划分为两个子问题，一个 naive，一个规模缩减。
算法分析：线性递归，使用递归跟踪，仅使用于简明的递归
example: 颠倒数组
任意给定数组 A[0, n), 将其中的子区间 A[lo, hi] 颠倒
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
void reverse (int* A, int lo, int hi)
{
if (lo < hi)
{
swap (A[lo], A[hi]);
reverse (A, lo++, hi--)
}
}
|
迭代：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
void reverse (int* A, int lo, int hi)
{
while(lo < hi)
{
swap(A[lo--], A[hi++])
}
}
|
分而治之 (divide and conquer)
求解一个大规模问题，可以将其划分为两个子问题，规模大体相当。
分别求解子问题
由子问题的解，得到原问题的解。
Example： MAX2，二分递归
从数组区间 A[lo,hi] 中找出最大的两个整数。
迭代解法
遍历整个数组，分别与 x1, x2 比较。
每迭代一次，比较 1/2 次。O(2n-3).
递归+分治解法
分而治之：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
|
void max2(int A[], int lo, int hi, int x1, int x2)
{
if (lo + 2 == hi) {* ... * ; return;}
if (lo + 3 == hi) {* ... * ; return;}
int mi = (lo + hi)/2;
int x1L, x2L;
max2(A, lo, mi, x1L, x2L);
int x1R, x2R;
max2(A, mi, hi, x1R, x2R);
if (A[x1L] > A[x1R])
{
x1 = x1L;
x2 = (A[x2L] > A[x1R]) ? x2L : x1R;
}
else
{
x1 = x1R;
x2 = (A[x1L] > A[x2R]) ? x1L : x2R;
}
}
|
动态规划
记忆法：example Fabonacci
$$fib(n)=fib(n-1)+fib(n-2)$$
1
2
3
4
5
6
7
8
9
|
int fib(n)
{
return (2 > n) ? n : fib(n-1) + fib(n-2);
}
|
速度很慢很慢！ 因为大量的递归实例被重复的调用。
解决方法：
这个可以类比上台阶，每一步可以是 1 或 2 级台阶。
那么走到第 n 级台阶的方式是 第 n-1 阶 和 第n-2 阶的方式之和。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
f = 1; g = 0;
while( 0 < n-- )
{
g = g + f;
f = g - f;
}
return g;
|
不断的从下而上的更新 g, f.
example: LCS (longest common sequence)
题目详情（子序列不同于子串，子序列可以是不连续的）：
思考：从递归的角度去想，缩小规模无非是 分而治之 和 减而治之。
将规模缩小，A[0, n], B[0, m], LCS[A, B] 只有三种情况：
n=-1 或 m=-1, 则为空
A[n] = B[m] = “X”, 减而治之，同时缩小两个字串 LCS(A[0, n-1], B[0, m-1]) + “X”
$A[n] \ne B[m]$, 分而治之，LCS(A[0, n-1], B[0,m]) 和 LCS(A[0, n],B[0, m-1]) 中的较大值。
分析算法的可行性：
解决这种递归实例反复调用的方法：
从上图可以很清楚的明白制表的过程，每一个递归实例都可能被反复的经过。
比如： $A[n] \ne B[m]$. 那么分为两条路径： LCS(A[0, n-1], B[0,m]) 和 LCS(A[0, n],B[0, m-1]). 这两个的计算都需要计算 LCS(A[0, n-1], B[0,m-1]), 所以会造成重复计算。
所以如何制表呢？
递归公式， 用 $C[i,j]$ 来表示表格中 $[A_i, B_j]$ 处的长度。
具体填表的过程参考： https://blog.csdn.net/hrn1216/article/details/51534607
想清楚表格的物理意义： 可以看作某一个序列固定（列），然后逐渐增加另一个序列的长度（行），也就是逐渐填入行。
初始的情况也要想清楚，某一个序列长度为 0 时，公共序列肯定也为 0。
$m\times n$ 的表格
初始化， i=0 或 j=0
先填入第一行，一个字符为 “3”，没有与之相同的字符，所有这一行都为 0.
再填入第二行，填 [2,1] 处，都为3，C[2,1]=C[1,1]+1，然后按照递归公式走下去。
第二行其他空格 $A[i]\ne B[j]$，C[i,j]=max(C[i-1,j], C[i, j-1])
回溯构造 LCS
我们根据递归公式构建了上表，我们将从最后一个元素c[8][9]倒推出S1和S2的LCS。
C[8, 9] = 5，且$S_1[8] \ne S_2[9]$，所以倒推回去，C[8,9]的值来源于 C[8,8]的值(因为C[8,8] > c[7,9])
C[8, 8] = 5, 且 $S_1[8] = S_2[8]$, 所以倒推回去，C[8,8]的值来源于 C[7, 7]。
可能会出现分歧的情况，$S_1[i] \ne S_2[j]$, 且 C[i-1,j]=C[i, j-1]. 这个时候选择一个方向。
两种结果：
分歧处选择另一个方向。
时间复杂度分析： 构建表格需要 O(mn), 回溯输出一个 LCS 需要 O(m+n)
leetcode 300. Longest increasing sequence
Given an unsorted array of integers, find the length of longest increasing subsequence.
Example:
Input: [10,9,2,5,3,7,101,18]
Output: 4
Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.
Note:
There may be more than one LIS combination, it is only necessary for you to return the length.
Your algorithm should run in O(n2) complexity.
Follow up: Could you improve it to O(n log n) time complexity?
Brute Force [Time Limit Exceeded]: recursive
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
|
int lenofLIS(vector<int> &nums, int prev, int curpos);
class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
return lenofLIS(nums, INT_MIN, 0);
}
};
int lenofLIS(vector<int> &nums, int prev, int curpos){
if (curpos == nums.size())
return 0;
int taken = 0;
if (nums[curpos] > prev)
taken = 1 + lenofLIS(nums, nums[curpos], curpos+1);
int notaken = lenofLIS(nums, prev, curpos+1);
return max(taken, notaken);
}
|
时间复杂度分析：
数组中每一个位置都可能出现或者不出现在 LIS 中，也就是说每一个递归实例的操作是 2，所以最终时间复杂度是 $O(2^n)$
空间复杂度分析：$O(n^2)$
Recursion with memorization [Memory Limit Exceeded]
解决上面这种递归实例反复调用的问题，通常有两种方法，在上面学习中也说到了。这里先采用记忆法，将所有子问题列成一张表。
Dynamic Programming [Accepted]
参考： https://www.geeksforgeeks.org/longest-increasing-subsequence-dp-3/
Optimal Substructure:
Let arr[0..n-1] be the input array and L(i) be the length of the LIS ending at index i such that arr[i] is the last element of the LIS.
Then, L(i) can be recursively written as:
L(i) = 1 + max( L(j) ) where 0 < j < i and arr[j] < arr[i]; or
L(i) = 1, if no such j exists.
To find the LIS for a given array, we need to return max(L(i)) where 0 < i < n.
Thus, we see the LIS problem satisfies the optimal substructure property as the main problem can be solved using solutions to subproblems.
Following is a simple recursive implementation of the LIS problem. It follows the recursive structure discussed above.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
|
int lenofLIS(vector<int> &nums, int prev, int curpos);
class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
if (nums.size() == 0) return 0;
int dp[nums.size()];
dp[0] = 1;
for (int i=1; i< nums.size(); i++){
dp[i] = 1;
for (int j=0; j < i; j++){
if (nums[i] > nums[j] && dp[i] < dp[j]+1){
dp[i] = dp[j] + 1;
}
}
}
return *max_element(dp, dp+nums.size());
}
};
|
复杂度分析：
Time complexity: $O(n^2)$ Two loops of n.
Space complexity: $O(n)$ dp array size n is used.
总结
再回过头思考下动态规划的含义：
动态规划常常适用于有重叠子问题[1]和最优子结构性质的问题，动态规划方法所耗时间往往远少于朴素解法。
动态规划背后的基本思想非常简单。大致上，若要解一个给定问题，我们需要解其不同部分（即子问题），再根据子问题的解以得出原问题的解。
通常许多子问题非常相似，为此动态规划法试图仅仅解决每个子问题一次，从而减少计算量：一旦某个给定子问题的解已经算出，则将其记忆化存储，以便下次需要同一个子问题解之时直接查表。这种做法在重复子问题的数目关于输入的规模呈指数增长时特别有用。
对于 longest increasing subsequence 里面就存在最有子问题。对于一个序列，每增加一个元素，都可以看作一个子问题。
子问题的解是固定的，但是子问题与当前步的结合又是动态变化的。比如这里，当前 i 位置的值大于 j 的值和小于 j 的值的处理方式就不太一样。我们要做的就是找出这个规律 （递推公式），然后根据填写好的子问题的解的表格，进一步扩大问题规模。
所以如前面所说，动态规划：自顶而下递归，自底而上迭代。
