学习笔记 | 《算法导论》之从入门到放弃（2）

《算法导论》打卡2，主要内容：渐进记号，分治策略，最大子数组问题,矩阵乘法的strassen算法

第三章 函数的增长

• 当输入规模足够大，使得只有运行时间的增长量级有关时，我们要研究算法的渐进效率。也就是说，我们关心当输入规模无限增加时，在极限中，算法的运行时间如何随着输入规模的变大而增加。

  3.1 渐进记号

• 用来描述算法渐进运行时间的记号根据定义于为自然数集N={0，1，2，…}的函数来定义

3.1.1 Θ记号

• Θ记号：对一个给定的函数g(n)，用Θ(g(n))来表示以下函数的集合：
  Θ(g(n))={f(n):存在正常量c1,c2和n0,使得对所有n≥n0,有0≤c1*g(n)≤f(n)≤c2*g(n)}
• 

3.1.2 O记号

• O记号：当只有一个渐进上界时，使用O记号，对于一个给定的函数g(n)，用O(g(n))来表示以下函数的集合：
  O(g(n))={f(n):存在正常量c和n0，使得对所有n≥n0，有0≤f(n)≤c*g(n)}

3.1.3 Ω记号

• Ω记号：渐进下界。使用Ω记号，对于一个给定的函数g(n)，用Ω(g(n))来表示以下函数的集合：
  Ω(g(n))={f(n):存在正常量c和n0，使得对所有n≥n0，有0≤c*g(n)≤f(n)}

• 定理：对任意两个函数f(n)和g(n),我们有f(n)=Θ(g(n))，当且仅当f(n)=O(g(n))且f(n)=Ω(g(n))

3.1.4 o记号

• o记号：表示非渐进紧确的上界
  o(g(n))={f(n):对于任意正常书c>0,存在常量n0＞0，使得对所有n≥n0，有0≤f(n)＜c*g(n)}

3.1.5 w记号

• w记号：表示非渐进紧确的下界
  w(g(n))={f(n):对任意正常量c＞0，存在常量n0＞0，使得对所有n≥n0，有0≤c*g(n)＜f(n)}

3.2 标准记号与常用函数

• 单调性
• 向下取整与向上取整符号
• 模运算
• 多项式
• 指数
• 对数
• 阶乘
• 多重函数
• 多重对数函数
• 斐波那契数

第四章 分治策略

• 分治策略的步骤：分解，解决，合并
• 递归情况：子问题足够大，需要递归求解
• 基本情况：子问题足够小，递归已“触底”
• 递归式：通过更小的输入上的函数值来描述一个函数
• 求解递归式的方法：
  • 代入法
  • 递归树法
  • 主方法

4.1 最大子数组问题

• 
• 由于时间原因，最大化利益不一定是最低价格买入，最高价格卖出，因为存在最高价格先于最低价格出现的可能
• 暴力破解方法：尝试每一对可能的买入卖出，只要卖出时间在买入时间之后即可。
• 问题交换：
• 
• 只有当数组中包含负数时，最大子数组问题才有意义，如果所有数组元素都是非负的，最大数组问题没有任何难度，因为整个数组的和肯定是最大的。
• 使用分治策略的求解方法：
• 
• python

#python3
#find max crossing subarray
def f_m_c_s(A,low,mid,high):
    left_sum=float('-inf')
    right_sum=float('-inf')
    temp_sum=0

    for i in range(mid,low-1,-1):
        temp_sum=temp_sum+A[i]
        if temp_sum>left_sum:
            left_sum=temp_sum
            max_left=i
    temp_sum=0
    for i in range(mid+1,high+1):
        temp_sum=temp_sum+A[i]
        if temp_sum>right_sum:
            right_sum=temp_sum
            max_right=i
    return max_left,max_right,left_sum+right_sum

#find maxmum subarray
def f_m_s(A,low,high):
    if high==low:
        return low,high,A[low]
    else:
        mid=(low+high)//2
        left_low,left_high,left_sum=f_m_s(A,low,mid)
        right_low,right_high,right_sum=f_m_s(A,mid+1,high)
        cross_low,cross_high,cross_sum=f_m_c_s(A,low,mid,high)
        if left_sum>=right_sum and left_sum>=cross_sum:
            return left_low,left_high,left_sum
        elif right_sum>=left_sum and right_sum>=cross_sum:
            return right_low,right_high,right_sum
        else:
            return cross_low,cross_high,cross_sum

def main():
    A=[-1,2,3,-4,7,6,3,-22,33,4]
    print(f_m_s(A,0,len(A)-1))

main()

• 其他解法如：c++解决n个整数的数列，不超过m的最大子数列和

#include<cstdio>
#include<cstring>
#include<iostream>
#include<cmath>
#define N 1000000
using namespace std;

int n;
int m;
int a[N];
int sum[N];
int x;
int ans;
int main()
 {
    scanf("%d%d",&n,&m);
    int l=1;int r=1;
    for(int i=1;i<=n;i++)
     {
        while(l<=r&&a[l]<i-m)l++;
        scanf("%d",&x);
        sum[i]=sum[i-1]+x;
        ans=max(ans,sum[i]-sum[a[l]]);
        while(l<=r&&sum[a[r]]>=sum[i])r--;
        a[++r]=i;
     }
    printf("%d",ans);
 }

4.2 矩阵乘法的Strassen算法

• c++如何创建动态二维数组：

#include<iostream>
using namespace std;

int main(){
    int n;
    cin>>n;
    int **a=new int*[n];
    for(int i=0;i<n;i++){
        a[i]=new int[n];
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            cin>>a[i][j];
        }
    }
}

• 
• python矩阵乘法暴力破解算法

def matrixMultiply(A,B):
    #len(A[0])是A的列数，len(A)是A的行数，B同理
    C = []
    if len(A[0]) != len(B):
         return false
    for i in range(len(A)):
        row=[]
        for j in range(len(B[0])):
            s = 0
            for k in range(len(A[0])):
                s += A[i][k]*B[k][j]
            row.append(s)
        C.append(row)
    return C 

def main():
    A = [[1,2,3],[4,5,6]]
    B = [[7,8],[9,10],[11,12]]
    C = matrixMultiply(A,B)
    for i in range(len(C)):
        for j in C[i]:
            print(j,end=" ")
        print("\n") 

if __name__ =="__main__":
    main()

• 方阵乘法的简单分治算法（前提：假定A,B都是n等于2的次幂的方阵）
• 
• python

def division(a):    #矩阵分块函数
    n=len(a)//2
    a11=[[0 for i in range(n)]for j in range(n)]
    a12=[[0 for i in range(n)]for j in range(n)]
    a21=[[0 for i in range(n)]for j in range(n)]
    a22=[[0 for i in range(n)]for j in range(n)]
    for i in range(n):
        for j in range(n):
            a11[i][j]=a[i][j]
            a12[i][j]=a[i][j+n]
            a21[i][j]=a[i+n][j]
            a22[i][j]=a[i+n][j+n]
    return (a11,a12,a21,a22)
 
def matrix_combination(a11,a12,a21,a22):
    n2 = len(a11)
    n=n2*2
    a = [[0 for col in range(n)] for row in range(n)]
    for i in range (0,n):
        for j in range (0,n):
            if i <= (n2-1) and j <= (n2-1):
                a[i][j] = a11[i][j]
            elif i <= (n2-1) and j > (n2-1):
                a[i][j] = a12[i][j-n2]
            elif i > (n2-1) and j <= (n2-1):
                a[i][j] = a21[i-n2][j]
            else:
                a[i][j] = a22[i-n2][j-n2]
    return a
def matrix_add(a,b):  #矩阵相加函数
    n = len(a)
    c = [[0 for col in range(n)] for row in range(n)]
    for i in range(0,n):
        for j in range(0,n):
            c[i][j] = a[i][j]+b[i][j]
    return c
 
def matrix_devision_multiply(a,b):   #矩阵乘法的简单分治法主程序
    n=len(a)
    c = [[0 for col in range(n)] for row in range(n)]#c=[[0]*n for i in range(n)]
    if n==1:
        c[0][0]=a[0][0]*b[0][0]
    else:
        (a11,a12,a21,a22)=division(a)
        (b11,b12,b21,b22)=division(b)
        (c11,c12,c21,c22)=division(c)
        c11=matrix_add(matrix_devision_multiply(a11,b11),matrix_devision_multiply(a12,b21))
        c12=matrix_add(matrix_devision_multiply(a11,b12),matrix_devision_multiply(a12,b22))
        c21=matrix_add(matrix_devision_multiply(a21,b11),matrix_devision_multiply(a22,b21))
        c22=matrix_add(matrix_devision_multiply(a21,b12),matrix_devision_multiply(a22,b22))
        c=matrix_combination(c11,c12,c21,c22)
    return c
 
a=[[1,1,1,1],[1,1,1,1],[2,2,2,2],[2,2,2,2]]
b=a
print(matrix_devision_multiply(a,b))

• 矩阵乘法的Strassen算法
  
  
  
  
  

def matrix_strassen(a,b):
    n=len(a)
    c = [[0 for col in range(n)] for row in range(n)]
    if n==1:
        c[0][0]=a[0][0]*b[0][0]
    else:
        (a11,a12,a21,a22)=division(a)
        (b11,b12,b21,b22)=division(b)
        (c11,c12,c21,c22)=division(c)
        s1=matrix_add_sub(b12,b22,0)
        s2=matrix_add_sub(a11,a12,1)
        s3=matrix_add_sub(a21,a22,1)
        s4=matrix_add_sub(b21,b11,0)
        s5=matrix_add_sub(a11,a22,1)
        s6=matrix_add_sub(b11,b22,1)
        s7=matrix_add_sub(a12,a22,0)
        s8=matrix_add_sub(b21,b22,1)
        s9=matrix_add_sub(a11,a21,0)
        s10=matrix_add_sub(b11,b12,1)
        p1=matrix_strassen(a11,s1)
        p2=matrix_strassen(s2,b22)
        p3=matrix_strassen(s3,b11)
        p4=matrix_strassen(a22,s4)
        p5=matrix_strassen(s5,s6)
        p6=matrix_strassen(s7,s8)
        p7=matrix_strassen(s9,s10)
        c11=matrix_add_sub(matrix_add_sub(matrix_add_sub(p5,p4,1),p2,0),p6,1)
        c12=matrix_add_sub(p1,p2,1)
        c21=matrix_add_sub(p3,p4,1)
        c22=matrix_add_sub(matrix_add_sub(matrix_add_sub(p5,p1,1),p3,0),p7,0)
        c=matrix_combination(c11,c12,c21,c22)
    return c
 
#矩阵的strssen算法
def division(a):                              #对矩阵进行分解操作
    n=len(a)//2
    a11=[[0 for i in range(n)]for j in range(n)]
    a12=[[0 for i in range(n)]for j in range(n)]
    a21=[[0 for i in range(n)]for j in range(n)]
    a22=[[0 for i in range(n)]for j in range(n)]
    for i in range(n):
        for j in range(n):
            a11[i][j]=a[i][j]
            a12[i][j]=a[i][j+n]
            a21[i][j]=a[i+n][j]
            a22[i][j]=a[i+n][j+n]
    return (a11,a12,a21,a22)
 
def matrix_add_sub(a,b,keys):
    n = len(a)
    c = [[0 for col in range(n)] for row in range(n)]
    if keys==1:
        for i in range(n):
            for j in range(n):
                c[i][j] = a[i][j]+b[i][j]
    else:
        for i in range(n):
            for j in range(n):
                c[i][j]=a[i][j]-b[i][j]
    return c
def matrix_combination(a11,a12,a21,a22):    #对矩阵进行组合操作
    n2 = len(a11)
    n=n2*2
    a = [[0 for col in range(n)] for row in range(n)]
    for i in range (0,n):
        for j in range (0,n):
            if i <= (n2-1) and j <= (n2-1):
                a[i][j] = a11[i][j]
            elif i <= (n2-1) and j > (n2-1):
                a[i][j] = a12[i][j-n2]
            elif i > (n2-1) and j <= (n2-1):
                a[i][j] = a21[i-n2][j]
            else:
                a[i][j] = a22[i-n2][j-n2]
    return a
 
a=[[1,1,1,1],[1,1,1,1],[2,2,2,2],[2,2,2,2]]
b=a
print(matrix_strassen(a,b))