算法设计技巧与分析题型整理（考试向）

本文最后更新于：2024年6月8日 上午

算法设计与分析题目整理（考试向）

1.基础概念（问答题）

算法的5个重要特征

有穷性、可行性、确定性、输入、输出

元运算

总是以一个时间常量为上界，不管输入数据或执行的算法的计算步骤。

Eg：算术运算、比较运算、赋值运算

基本运算

如果一个元运算具有最高的频度，其他所有元运算频度均在它的频度的常数倍内，则称这个元运算为基本运算

Eg：排序算法中的元素比较运算、矩阵乘法中的数量乘法运算、遍历链表中的更新指针运算、图遍历中的对访问节点的“动作”

算法使用的空间

定义：为了求解问题的实例而执行的计算步骤所需要的内存空间

  • 不包括用来存储输入的空间，因为要区分那些在整个计算过程中占用了“少于”线性空间的算法

  • 算法的空间复杂性不可能超过运行时间的复杂性，S(n)=O(T(n))S(n)=O(T(n))

平摊分析

用来算出算法在整个执行过程中所用时间的平均值，称为平摊运行时间，用OO作为测度

  • 和平均时间分析不同，不用计算相同大小的所有实例才能得到平均值，也不用假设输入的概率分布

什么是子问题，其在算法设计中的作用

对于一个规模为 n 的问题将其分解为 k 个规模较小的子问题，这些子问题互相独立且与原问题形式相同，递归地解这些子问题，然后将各子问题的解合并得到原问题的解。

确定算法

确定算法：对于同一合法输入数据，该算法无论运行多少次，给出的输出是唯一的

反之为概率算法

不确定算法

不确定算法分为两步，它将一个判定问题的实例ll作为输入，

  1. 猜测（非确定）阶段：生成一个任意串SS，将其作为实例ll的一个候选解
  2. 验证（确定）阶段：确定算法把ll和SS作为其输入，如果SS是ll的一个解，输出是；否则输出否或者不停止

不确定多项式类型算法

验证阶段是多项式时间内的不确定算法

P/NP/NPH/NPC

  1. P类问题：能用确定性算法在多项式时间内求解的问题，也称多项式类型
  2. NP类问题：可以用不确定多项式算法求解的判定问题，也称不确定多项式类
    • 区别：P类问题可以用确定性算法在多项式时间内判定或求解；NP类问题可以用确定性算法在多项式时间内检查或验证
  3. NPC类问题：如果一个问题D，属于NP类型、NP中的任何问题都可以在多项式时间内化简为D，则称D为NPC类问题。Eg：哈密顿回路问题、旅行商问题、点着色问题、划分问题、背包问题
  4. NPH类问题：如果一个问题D，NP中的任何问题都可以在多项式时间内化简为D，则称D为NPH类问题

2.排序相关

有n张卡片排成一行，并且有n个不同的数字写在卡片上(每张卡片上一个)，使得卡片呈降序排列状态。现在允许你交换任何一对卡片的位置，只要它们之间只有一张卡片即可。对于什么样的n值，在这样一组操作序列以后，能使得卡片呈升序排列？如果这样n值存在的话，请设计使得交换次数最小的算法，并给出最小的交换次数是多少次。

  1. 由于每次交换只能交换同样在奇数位置或者偶数位置的数

    如果nn为奇数，能够使得卡片升序排列

    如果nn为偶数则无法实现，因为最大的卡片在11（奇数位置），无法交换到最后一个位置nn（偶数位置）

  2. 我们可以考虑将其分为奇数和偶数分开交换，当nn为奇数时，序列中奇数个数为(n+1)/2(n+1)/2，偶数个数为(n−1)/2(n-1)/2.

    • 对于奇数，需要交换次数：0+1+...+(n−1)/2=(n2−1)/80+1+...+(n-1)/2=(n^2-1)/8
    • 对于偶数，需要交换次数：0+1+...+(n−3)/2=(n2+3−4n)/80+1+...+(n-3)/2=(n^2+3-4n)/8

    总交换次数：(n2−2n+1)/4(n^2-2n+1)/4

  3. 此交换次数一定是最小的交换次数，因为每次交换只能改变一个元素在序列中的顺序

数组A[1,2,...,n]A[1,2,...,n]存放了nn个无序的各不相同的数，0<k<n0<k<n，k=Θ(n/log n)k=\Theta(n/log\ n)，请设计算法求出AA中最小的kk个元素，并按从小到大的顺序存储到B[1,2,...,k]B[1,2,...,k]中，要求：

  1. 算法的时间复杂度为Θ(n)\Theta(n)，算法步骤中给出必要注释
  2. 证明时间复杂度满足以上要求

3.归纳法

令A[1..n]A[1..n]是一个nn个整数的已经排好序的数组，xx是整数。请设计一个O(n)O(n)的算法来确定在AA中是否存在两个数，和恰好是xx.

可采用双指针算法。初始i=1,j=ni=1,j=n，当A[j]+A[i]>xA[j]+A[i]>x时将jj向左移，结束后如果j==ij==i则不存在；否则判断是否有A[j]+A[i]==xA[j]+A[i]==x，若有则存在；否则将ii向右移，继续循环。

1
2
3
4
5
6
7
8
9
10
11
12
13
bool judge(int A[],int n,int x){
    int i=1,j=n;
    while(i<j){
        while(j>i && A[j]+A[i]>x)
            j--;
        if(j==i)	break;
        if(A[j]+A[i]==x)
            return true;
        else if(A[j]+A[i]<x)
            i++;
	}
    return false;
}

有n张大小各不相同的薄饼，一张叠在另一张上面。允许用一个翻板插到一个薄饼下面，然后可以把板上面的这叠薄饼翻个身。目标是根据薄饼的大小重新安排它们的位置，最大的饼要放在最下面。

  1. 利用归纳法算法设计策略给该问题设计一个算法(用自然语言描述算法过程即可)
  2. 上述算法的时间复杂性是多少?（时间复杂性即翻板翻动的次数，要求写出算法的递推式，从递推式求解）
  1. 第一次，找到11到nn中最大的薄饼，将其上面的饼一起翻身，然后将所有的薄饼一起翻身，这样最大的薄饼就在下面；第二次，找到11到n−1n-1中最大的薄饼，翻身后，重复第一次的翻身过程，这样第二大的薄饼在倒数第二层；以此类推，直到翻到最顶上一层薄饼。
  2. T(n)=T(n−1)+2,T(1)=0T(n)=T(n-1)+2,T(1)=0，因此T(n)=2n−2T(n)=2n-2，时间复杂度Θ(n)\Theta(n)

名流问题:在总人数为n的人群中的名流，就是指不认识任何人，所有其他人却都认识的人。问题的任务是:仅仅通过向人们提出形如“你是否认识某某
的问题，来识别出名流。

为简化该问题，假设在给定总人数为nn的人群中存在名流，该问题可以采用下述"每次减一”的算法来解。

  1. 如果n=1n=1，则根据定义，这仅有的一个人肯定是名流

  2. 如果n>1n>1，则从人群中任选两人甲和乙，并问甲是否认识乙。如果甲认识乙，则将甲从可能成为名流的其余人中移除；如果甲不认识乙，则移除乙。然后，对其余n−1n-1个可能成为名流的人群。采用递归方式求解即可

4.分治法

设AA是nn个实数构成的数组, 设计一个算法重新排列数组中的数, 使得负数都排在正数前面. 要求算法使用 O(n)O(n) 的时间和 O(1)O(1) 的空间.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void reSort(int A[],int n){
    int i=1,j=n;
    while(i<j){
        if(A[i]<0){
            i++;
            continue;
        }
        if(A[j]>0){
            j--;
            continue;
        }
        if(A[i]>0 && A[j]<0){
            swap(A[i],A[j]);
        	i++,j--;
        }
    }
}

由于i>=ji>=j时停止，所以共遍历数组一遍，时间复杂度O(n)O(n)；额外用的空间为i,ji,j和swapswap中的变量，因此为O(1)O(1)

A[1..n]A[1..n]和B[1..n]B[1..n]是两个已经按升序排列的互不相同整数组成的数组，求AA和BB合起来以后2n2n个元素的中项，分析时间复杂度

令k=⌈n/2⌉k=\lceil n/2\rceil，则A[k]A[k]和B[k]B[k]分别是AA和BB中的中位数，合并后的中位数位置为nn

  1. 若A[k]=B[k]A[k]=B[k]，则合并后中位数就是A[k]A[k]
  2. 若A[k]<B[k]A[k]<B[k]，则A[1,...,k−1]A[1,...,k-1]中、B[k+1,...,n]B[k+1,...,n]中不含中位数，合并后中位数一定在A[k,...,n]A[k,...,n]和B[1,...,k]B[1,...,k]中
  3. 若A[k]>B[k]A[k]>B[k]，则A[k+1,...,n]A[k+1,...,n]中、B[1,k−1]B[1,k-1]中不含中位数，合并后中位数一定在A[1,...,k]A[1,...,k]和B[k,...,n]B[k,...,n]中
  4. 最终若只剩1个元素，返回min(A,B)min(A,B)
1
2
3
4
5
6
7
8
9
10
11
12
13
getMiddleNumber(A[],al,ar,B[],bl,br):
    #数组元素个数
    n=ar-al+1
    if(n==1) then 
    	return min(A[al],B[bl])
    ka=al+ceil(n/2)-1
    kb=bl+ceil(n/2)-1
    if(A[ka]==B[kb]) then 
    	return A[ka]
    else if(A[ka]<B[kb]) then
    	return getMiddleNumber(A[],ka,n,B[],1,kb)
    else if(A[ka]>B[kb]) then
    	return getMiddleNumber(A[],1,ka,B[],kb,n)

5.回溯法

用回溯法输出1~N(N个不重复正整数)的全排列

  1. 用自然语言描述算法思想
  2. 以N=3为例子，画出解空间树
  3. 写出伪代码程序

  1. 可以采用深度优先遍历的思想，采用标记数组标记当前正在处理的排列中已遍历过的数。递归时记录访问的层数（即已经遍历的整数的个数）。在每次递归时访问未被标记的数，并将其标记加入答案中，进入下一层递归，下一层递归结束后需要重新将其标记为未访问，并从答案中弹出该数。当递归访问的层数为n+1时，代表此时的答案st就是一个全排列，将其加入答案集合中即可。

  2. 如下

    flowchart TB
	N(n)
	1(1)
	2(2)
	3(3)
	4(2)
	5(3)
	6(1)
	7(3)
	8(1)
	9(2)
	10(3)
	11(2)
	12(3)
	13(1)
	14(2)
	15(1)
	N---1
	N---2
	N---3
	1---4
	1---5
	2---6
	2---7
	3---8
	3---9
	4---10
	5---11
	6---12
	7---13
	8---14
	9---15

  3. 用bool数组visit[i]记录数ii是否正在被访问，用数组st记录每个全排列，用数组ans记录所有的全排列字符串

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    permutation(n,k):
        if(k==n+1) then
        	将st转化为排列字符串s
        	将s加入ans
            return
        for i=1 to n:
            if(visit[i]==false) then
            	将i压入st
            	visit[i]=true
                permutation(n,k+1)
                visit[i]=false
                将i弹出st
            else continue
        endfor
    permutation(n,1)

6.动态规划

递推

给出一个mm行nn列的矩阵AA，甲需要从A11A_{11}走到AmnA_{mn}，只能向右或向下走一格。请设计O(m∗n)O(m*n)的动态规划算法，求出甲从A11A_{11}走到AmnA_{mn}路径上经历的元素之和的最小值（包括A11A_{11}和AmnA_{mn}）

  1. 给出最优解的表示方法，递推关系表达式
  2. 给出具体算法步骤
  3. 分析时间复杂度

  1. 设dp[i,j]dp[i,j]表示走到ii行jj列所用的最小值，则dp[i,j]=min(dp[i−1,j],dp[i,j−1])+Aijdp[i,j]=min(dp[i-1,j],dp[i,j-1])+A_{ij}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
minElemSum(A,m,n):
    dp[1][1]=A[1][1]
    #初始化第一列
    for i=2 to m:
        dp[i][1]=dp[i-1][1]+A[i][1]
    #初始化第一行
    for i=2 to n:
        dp[1][i]=dp[1][i-1]+A[1][i]
    for i=2 to m:
        for j=2 to n:
            dp[i][j]=min(dp[i-1,j],dp[i,j-1])+A[i][j]
        endfor
    endfor
    return dp[m][n]
  1. 时间复杂度m−1+n−1+(m−1)(n−1)=Θ(mn)m-1+n-1+(m-1)(n-1)=\Theta(mn)

计算组合数：从nn个物品中取出mm个的情况数CnmC_{n}^{m}，0≤m≤n0\le m\le n

  1. 给出递推式
  2. 采用什么数据结构记录已求得的解？初始条件是什么？
  3. 给出DP伪代码
  4. 分析时间复杂度和空间复杂度

  1. 对于CijC_{i}^{j}，从ii中取出jj个物品，Cij=Ci−1j+Ci−1j−1C_{i}^{j}=C_{i-1}^{j}+C_{i-1}^{j-1}

  2. 采用二维数组C[n][m]C[n][m]，初始条件为i∈[1,n],C[i][0]=C[i][i]=1i\in [1,n],C[i][0]=C[i][i]=1

1
2
3
4
5
6
7
8
9
10
solve(n,m):
    for i=1 to n:
        C[i][0]=C[i][i]=1
    endfor
    for i=2 to n:
        for j=1 to i-1: 
            C[i][j]=C[i-1][j]+C[i-1][j-1]
        endfor
    endfor
    return C[n][m]
  1. 时间复杂度为n+∑i=2n(i−1)=n+n2/2−n/2=Θ(n2)n+\sum_{i=2}^{n}(i-1)=n+n^2/2-n/2=\Theta(n^2)，空间复杂度为Θ(nm)\Theta(nm)

背包DP

零钱兑换：给你一个整数数组 coins，表示不同面额的硬币；以及一个整数amount，表示总金额。计算并返回可以凑成总金额所需的最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回-1 。每种硬币的数量是无限的。leecode链接

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        int dp[10010];
        memset(dp,0x3f,sizeof(dp));
        dp[0]=0;
        for(int i=1;i<=amount;i++){
            for(int j=0;j<coins.size();j++){
                if(i>=coins[j])
                    dp[i]=min(dp[i],dp[i-coins[j]]+1);
            }
        }
        return dp[amount]<0x3f3f3f3f?dp[amount]:-1;
    }
};

dp(i)dp(i)表示总金额为ii时的最少硬币个数，则dp(i)=min{dp(i−coins[j])}(1≤j≤n)+1dp(i)=min\{dp(i-coins[j])\}(1\le j\le n)+1.

线性DP

某人打算开设奶茶店，有nn个位置可以选择，若在第ii个位置开设，则后面连续ff个位置不能开设，其中ff为已知正整数。假设在第ii个位置开设奶茶店的预期收益为pi(pi>0)p_i(p_i>0)，设计一种动态规划算法，用于找出一种最佳开设方案，使得总预期收益最大，给出设计关键步骤和伪代码，并分析时间和空间复杂度。

1
2
3
4
5
6
7
8
9
10
11
12
GetMaxProfit(p[],n,f):
	dp[1]=p[1]
	for i=2 to n:
    	#不选i
        dp[i]=dp[i-1]
        #选i
        if(i-f-1>=1)
        	dp[i]=max(dp[i],dp[i-f-1]+p[i])
        else
        	dp[i]=max(dp[i],p[i])
    endfor
    return dp[n]

时间复杂度Θ(n)\Theta(n)，空间复杂度Θ(n)\Theta(n)

区间DP

对应书上例题：矩阵链相乘

将1,2,...,N1,2,...,N堆石头有次序的合成一堆，每堆石子包含的石子个数给定，规定每次只能选相邻的2堆石子合成新的一堆，并将新的一堆石子数记为该次合并的得分

  1. 假设要求计算出将N堆石子合并成一堆的最小得分值，写出动态规划的递归方程，分析能否用递归程序实现;
  2. 设计一个动态规划程序（伪代码），计算出将n堆石头合成一堆的最小得分值
  3. 分析设计算法的时间复杂度
  4. 如果要得到取得最小得分的合并方案，如何修改程序？分析该方法的空间复杂度（合并方案可以加括号表示）

设m[i]m[i]为第ii堆石头的个数，psum[i]psum[i]表示1−i1-i堆石头的总个数，因此区间[i,j][i,j]的石头总个数为psum[j]−psum[i−1]psum[j]-psum[i-1]

  1. 用dp(i,j)dp(i,j)表示将区间[i,j][i,j]内的石头合并在一起的最小得分

    则dp(i,j)=psum[j]−psum[i−1]+min{dp(i,k)+dp(k+1,j)}(i≤k≤j−1)dp(i,j)=psum[j]-psum[i-1]+min\{dp(i,k)+dp(k+1,j)\}(i\le k\le j-1)

    由于求解dp(i,j)dp(i,j)需要求解其中此区间所有的划分，因此可以用递归实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
minScore(m[],n)
	将dp数组全部初始化为INF
	for i=1 to n:
        psum[i]=psum[i-1]+m[i]
        dp[i][i]=0
    endfor
    #枚举区间长度
	for len=2 to n:
        #枚举区间起点
        for i=1 to n-len+1:
            #确定区间终点
            j=i+len-1
            #枚举子区间
            for k=i to j-1:
                dp[i][j]=min(dp[i][j],psum[j]-psum[i-1]+dp[i][k]+dp[k+1][j])
            endfor
        endfor
    endfor
    return dp[1][n]

  1. 时间复杂度为

    n+∑l=2n∑i=1n−l+1(l−1)=n+∑l=2n(n−l+1)(l−1)=n+∑l=2n((n+2)l−l2−(n+1))=n−(n+1)(n−1)+(n+2)(2+3+...+n)−(22+32+...+n2)=n−n2+1+n3/2−n2/2+n2−n−n3/3−n2/2−n/6+1=Θ(n3)\begin{align} n+\sum_{l=2}^{n}\sum_{i=1}^{n-l+1}(l-1)&=n+\sum_{l=2}^{n}(n-l+1)(l-1)\\ &=n+\sum_{l=2}^{n}((n+2)l-l^2-(n+1))\\ &=n-(n+1)(n-1)+(n+2)(2+3+...+n)-(2^2+3^2+...+n^2)\\ &=n-n^2+1+n^3/2-n^2/2+n^2-n-n^3/3-n^2/2-n/6+1\\ &=\Theta(n^3) \end{align}

  2. 要求出合并的方案，需要知道dp(i,j)dp(i,j)是从哪一步更新而来，因此我们可以用二维数组ans[i][j]ans[i][j]记录区间[i,j][i,j]最优的划分位置kk，在枚举子区间的时候，改为以下代码：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    #枚举区间长度
    for len=2 to n:
        #枚举区间起点
        for i=1 to n-len+1:
            #确定区间终点
            j=i+len-1
            #枚举子区间
            for k=i to j-1:
               	temp=psum[j]-psum[i-1]+dp[i][k]+dp[k+1][j]
               	if(dp[i][j]<temp)
                   	dp[i][j]=temp
                    #在第k个位置划分
                    #(i,j)=(i,k)+(k+1,j)
                    ans[i][j]=k
            endfor
        endfor
    endfor

    用ans1ans1数组存储括号。如果ans1[i]='('，表示在ii的左侧需要加(；如果ans1[i]=')'，表示在ii的右侧需要加)

    以下为得到划分方案的函数：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    GetSplit(i,j):
        if(i>=j) return
    	k=ans[i][j]
    	ans1[i]='('
        ans1[k]=')'
        ans1[k+1]='('
        ans1(j)=')'
        GetSplit(i,k)
        GetSplit(k+1,j)

    空间复杂度为Θ(n2)\Theta(n^2)

若石堆成圆形排列（即首尾相连），如何求解？

答：考虑将石堆1−N1-N延长为1−2N1-2N，其中1=N+1,2=N+2...1=N+1,2=N+2...，用动态规划求解后，取用动态规划求解后，取 dp(1,n),dp(2,n+1),…,dp(n−1,2n−2)dp(1,n),dp(2,n+1),\dots,dp(n-1,2n-2)中的最优值即可

最长回文子序列：给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度。子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。实例：bbbab、cbbd。leecode链接

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int longestPalindromeSubseq(string s) {
    int dp[1010][1010];
    memset(dp,0,sizeof(dp));
    int n=s.size();
    s=' '+s;
    for(int i=1;i<=n;i++){
        dp[i][i]=1;
    }
    //枚举区间
    for(int l=2;l<=n;l++){
        //枚举起点
        for(int i=1;i<=n-l+1;i++){
            int j=i+l-1;
            if(s[i]==s[j]){
                dp[i][j]=dp[i+1][j-1]+2;
            }
            else{
                dp[i][j]=max(dp[i+1][j],dp[i][j-1]);
            }
        }
    }
    return dp[1][n];
}
#算法设计
算法设计技巧与分析题型整理（考试向）
http://kcollision.github.io/2024/0654233905.html
作者
collision
更新于
2024年6月8日
许可协议