算法导论--第一部分（基础知识）

第1章算法在计算中的作用

1.1 算法

算法是任何良定义的计算过程，该过程取某个值或值的集合作为输入并产生某个值或者值的集合作为输出。

对每个输入实例，算法都以正确的输出停机，则称该算法是正确的。

算法的运行时间：

$log{n} < sqrt{n} < n < nlog{n} < n^2 < n^3 < 2^n < n!$

第2章算法基础

2.1 插入排序

原址排序，只需要O(1)的额外空间

 1 def insertion_sort(nums):
 2     for i in range(1,len(nums)):
 3         tmp = nums[i]
 4         j = i - 1 
 5         while j>=0 and nums[j] > tmp:
 6             nums[j+1] = nums[j]
 7             j -= 1
 8         nums[j+1] = tmp
 9     return nums
10 
11 print(insertion_sort([4,3,2,2,1,5]))

循环不变式：主要用来帮助我们理解算法的正确性

关于循环不变式，我们必须证明三条性质：

初始化：循环的第一次迭代之前，它为真

保持：如果循环的某次迭代之前它为真，那么下次迭代之前它仍未为真（这里可以用形式化证明，也可以用非形式化分析）

终止：在循环终止时，不变式为我们提供一个有用的性质，该性质有助于证明算法是正确的。（证明在循环终止时，确实得到了我们想要的结果）

若要求证明算法的正确性，需要使用循环不变式的方式

2.2 分析算法

运行时间：指执行的基本操作数或步数（假定执行每行伪代码需要常量时间）

一般研究最坏情况运行时间，即对规模为n的任何输入，算法的最长运行时间

增长量级：只考虑运行时间的增长率或增长量级，即只考虑公式中的高阶项，比如插入排序最坏情况运行时间是$O(n^2)$

2.3 设计算法

插入排序使用了增量的方法，还有“分治法”

分治法：将原问题分解为几个规模较小但类似于原问题的子问题，递归地求解这些子问题，然后再合并这些子问题的解来建立原问题的解。

分解原问题为若干子问题，这些子问题是原问题的规模较小的实例
解决这些子问题，递归地求解各子问题。然而，若子问题规模足够小，则直接求解
合并这些子问题的解成原问题的解

 1 def merge_sort(nums):
 2     if len(nums) == 1:
 3         return [nums[0]]
 4     mid = len(nums)//2
 5     left_part = merge_sort(nums[0:mid])
 6     right_part = merge_sort(nums[mid:])
 7     return merge(left_part,right_part)
 8 
 9 def merge(left,right):
10     res = []
11     i = j = 0
12     while i<len(left) and j<len(right):
13         if left[i]<=right[j]:
14             res.append(left[i])
15             i += 1
16         else:
17             res.append(right[j])
18             j += 1
19     if i==len(left):
20         res += right[j:]
21     else:
22         res += left[i:]
23     return res
24 
25 print(merge_sort([2,4,5,7,1,2,3,6]))

上面这个版本感觉有点费空间，每次切片操作都要进行复制，然后再传入新的地址，所以更好一点的做法，是传入原数组地址，和相应的index

 1 def merge_sort(nums,i,j):
 2     if j-i == 1:
 3         return [nums[i]]
 4     mid = (i+j)//2
 5     merge_sort(nums,i,mid)
 6     merge_sort(nums,mid,j)
 7     merge(nums,i,mid,j)
 8 
 9 def merge(nums,i,mid,j):
10     L = nums[i:mid]
11     R = nums[mid:j]
12     a = b = 0
13     k = i
14     while a<mid-i and b<j-mid:
15         if L[a]<=R[b]:
16             nums[k] = L[a]
17             a += 1
18         else:
19             nums[k] = R[b]
20             b += 1
21         k += 1
22     if a==mid-i:
23         nums[k:j] = R[b:]
24     else:
25         nums[k:j] = L[a:]
26     
27 nums = [2,4,5,7,1,2,3,6]
28 merge_sort(nums,0,8)
29 print(nums)

分析分治算法

当一个算法包含对其自身的递归调用时，可以用递归方程或递归式来描述其运行时间，然后求解该递归式给出算法性能的界

$T(n) = left{ egin{array}{ll} O(1) & nleq c\ aT(n/b) +D(n)+C(n) & other end{array} ight.$

把原问题分解成a个子问题，子问题的规模是原问题的1/b,分解问题成子问题要D(n),合并子问题的解成原问题的解需要时间C(n)

归并排序算法的分析：

$T(n) =left{egin{array}{ll} O(1) & n=1\ 2T(n/2) + O(n) & n>1end{array} ight.$

根据主定理可以解出 $T(n)=O(nlogn)$

如果不用主定理，也可以用递归树来求解运行时间的上界

第3章函数的增长

3.1 渐进记号

$Theta$记号渐进紧确界

$Theta(g(n))={f(n):exists c_1,c_2,n_0, forall ngeq n_0, that, 0leq c_1g(n)leq f(n)leq c_2g(n)}$

若存在正常量$c_1$和$c_2$使得足够大的$n$,函数$f(n)$能“夹入”$c_1g(n)$与$c_2g(n)$之间，则$f(n)$属于集合$Theta(g(n))$

$O$记号渐进上界

$Omega$记号渐进下界

3.2 标准记号与常用函数

向上取整$lceil x ceil$与向下取整$lfloor x floor$

多重对数函数：

lg*2 = 1 lg*4 = 2 lg*16 = 3 lg*65536 = 4 lg*($2^65536$) = 5

第4章分治策略

分治策略

分解：将问题划分为一些子问题，子问题的形式与原问题一样，只是规模更小
解决：递归地求解出子问题。如果子问题的规模足够小，这停止递归，直接求解
合并：将子问题的解组合成原问题的解

递归式：刻画分治算法的运行时间

三种求解递归式的方法：

代入法：猜测一个界，然后用数学归纳法证明这个界是正确的
递归树法：将递归式转换为一棵树，其结点表示不同层次的递归调用产生的代价。然后采用边界和技术来求解递归式
主方法：可求解右边公式的递归式的界 $T(n)=aT(n/b)+f(n)$

当递归式是等式的时候，求出来的就是紧确界用$Theta$记号，如果是小于等于，用$O$记号, 大于等于，用$Omega$记号

4.1 最大子数组问题

问题描述：给定一个数组A，求A中和最大的非空连续子数组

题目来源：给定一个数组，每个元素都是相应日期的股票价格，求什么时候买入，什么时候卖出，净收益最大，书中是将这个问题转换成了最大子数组进行分治算法求解。对应leetcode的121. Best Time to Buy and Sell Stock

暴力求解：两重循环遍历 $Omega(n^2)$，目标是设计出一个$o(n^2)$(非紧确上界)，即小于$n^2$复杂度

leetcode上解法非常美妙，也是转换成最大连续子数组用O(n)时间做

code：O(n) time O(1) space

 1 def maxProfit(self, prices):
 2         """
 3         :type prices: List[int]
 4         :rtype: int
 5         """
 6         maxCurrent = res = 0
 7         for i in range(1,len(prices)):
 8             maxCurrent = max(0,maxCurrent+prices[i]-prices[i-1])
 9             res = max(maxCurrent,res)
10         return res

为什么要转换问题呢，因为转换后的性质很好，求连续求和

书中采用分治策略求解该问题，分三种情况，完全在mid左边，横跨mid, 完全在mid右边；在左右两边的直接递归调用原函数就可以，对于横跨mid的情况需要单独处理，时间复杂度是O(n), 所以总的时间复杂度是O(nlogn)

code: O(nlogn)

 1 def find_maxmum_subarray(nums,low,high):
 2     if low==high:
 3         return nums[low]
 4     mid = (low + high)//2
 5     res_left = find_maxmum_subarray(nums,low,mid)
 6     res_cross = find_maxmum_subarray_cross_mid(nums,low,mid,high)
 7     res_right = find_maxmum_subarray(nums,mid+1,high)
 8     return max(res_left,res_cross,res_right)
 9 
10 def find_maxmum_subarray_cross_mid(nums,low,mid,high):
11     left_sum = 0
12     left_max = -float('inf')
13     for i in range(mid,low-1,-1):
14         left_sum += nums[i]
15         left_max = max(left_max,left_sum)
16     right_sum = 0
17     right_max = -float('inf')
18     for i in range(mid+1,high+1):
19         right_sum += nums[i] 
20         right_max = max(right_max,right_sum)
21     return left_max+right_max
22 
23 print(find_maxmum_subarray([13,-3,-25,20,-3,-16,-23,18,20,-7,12,-5,-22,15,-4,7],0,15))

分治算法主要就是考虑结果合并问题，和划分的第三种情况，考虑周到后就一定能正确实现

上述分治算法的分析：

$T(n)=left{egin{array}{ll} Theta(1) & n=1\ 2T(n/2)+Theta(n) & n>1end{array} ight.$

用主方法对上式求解得$T(n)=Theta(nlogn)$，也可以通过递归树的方法来理解为什么是$Theta(nlogn)$