课程布置的作业，遇事不决，度娘解决~

一、请谈谈你对算法复杂度的理解？

算法复杂度是指算法在编写成可执行程序后，运行时所需要的资源，资源包括时间资源和内存资源。

同一问题可用不同算法解决，而一个算法的质量优劣将影响到算法乃至程序的效率。算法分析的目的在于选择合适算法和改进算法。一个算法的优劣主要从算法的执行时间和所需要占用的存储空间两个方面衡量，即时间复杂度和空间复杂度。

1 时间复杂度

1.1 时间频度

一个算法执行所耗费的时间，从理论上是不能算出来的，必须上机运行测试才能知道。但我们不可能也没有必要对每个算法都上机测试，只需知道哪个算法花费的时间多，哪个算法花费的时间少就可以了。并且一个算法花费的时间与算法中语句的执行次数成正比例，哪个算法中语句执行次数多，它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度。记为T(n)。算法的时间复杂度是指执行算法所需要的计算工作量。

1.2 时间复杂度

在刚才提到的时间频度中，n称为问题的规模，当n不断变化时，时间频度T(n)也会不断变化。但有时我们想知道它变化时呈现什么规律。为此，我们引入时间复杂度概念。

一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数，用T(n)表示，若有某个辅助函数f(n),存在一个正常数c使得f(n)*c>=T(n)恒成立。记作T(n)=O(f(n)),称O(f(n)) 为算法的渐进时间复杂度，简称时间复杂度（Time complexity）。

在各种不同算法中，若算法中语句执行次数为一个常数，则时间复杂度为O(1)。另外，在时间频度不相同时，时间复杂度有可能相同，如T(n)=n^2+3n+4 与T(n)=4n^2 +2n+1它们的频度不同，但时间复杂度相同，都为O(n^2)。

按数量级递增排列，常见的时间复杂度有：

• 常数阶O(1)

• 对数阶O(log2n)(以2为底n的对数，下同)

• 线性阶O(n),

• 线性对数阶O(nlog2n)

• 平方阶O(n^2)

• 立方阶O(n^3),...，

• k次方阶O(n^k)

• 指数阶O(2^n)

随着问题规模n的不断增大，上述时间复杂度不断增大，算法的执行效率越低。

1.3 算法的时间性能分析

（1）算法耗费的时间和语句频度

一个算法所耗费的时间=算法中每条语句的执行时间之和

每条语句的执行时间=语句的执行次数(即频度(Frequency Count))×语句执行一次所需时间

算法转换为程序后，每条语句执行一次所需的时间取决于机器的指令性能、速度以及编译所产生的代码质量等难以确定的因素。

若要独立于机器的软、硬件系统来分析算法的时间耗费，则设每条语句执行一次所需的时间均是单位时间，一个算法的时间耗费就是该算法中所有语句的频度之和。

求两个n阶方阵的乘积 C=A×B,其算法如下:

# define n 100 // n 可根据需要定义,这里假定为100
void MatrixMultiply(int A[n][n]，int B[n][n]，int C[n][n])
{ //右边列为各语句的频度
    int i, j, k;
    for(i=0; i<n; i++) {  //n+1
        for (j=0; j<n; j++) { //n*(n+1)
                C[i][j] = 0; //n²
                for (k=0; k<n; k++) {  //n²*(n+1)
                    C[i][j] = C[i][j] + A[i][k] * B[k][j];  //n³
                }
            }
    }
}

该算法中所有语句的频度之和(即算法的时间耗费)为：

T(n)=2n³+3n²+2n+1

分析：

语句(1)的循环控制变量i要增加到n，测试到i=n成立才会终止。故它的频度是n+1。但是它的循环体却只能执行n次。语句(2)作为语句(1)循环体内的语句应该执行n次，但语句(2)本身要执行n+1次，所以语句(2)的频度是n(n+1)。同理可得语句(3)，(4)和(5)的频度分别是n2，n2(n+1)和n3。

算法MatrixMultiply的时间耗费T(n)是矩阵阶数n的函数。

（2）问题规模和算法的时间复杂度

算法求解问题的输入量称为问题的规模(Size)，一般用一个整数表示。

矩阵乘积问题的规模是矩阵的阶数。

一个图论问题的规模则是图中的顶点数或边数。

一个算法的时间复杂度(Time Complexity, 也称时间复杂性)T(n)是该算法的时间耗费，是该算法所求解问题规模n的函数。当问题的规模n趋向无穷大时，时间复杂度T(n)的数量级(阶)称为算法的渐进时间复杂度。

算法MatrixMultiply的时间复杂度T(n)如(1.1)式所示，当n趋向无穷大时，显然有T(n)~O(n^3);

这表明，当n充分大时，T(n)和n³之比是一个不等于零的常数。即T(n)和n³是同阶的，或者说T(n)和n³的数量级相同。记作T(n)=O(n³)是算法MatrixMultiply的渐近时间复杂度。

（3）渐进时间复杂度评价算法时间性能

主要用算法时间复杂度的数量级(即算法的渐近时间复杂度)评价一个算法的时间性能。

算法MatrixMultiply的时间复杂度一般为T(n)=O(n³)，f(n)=n³是该算法中语句(5)的频度。下面再举例说明如何求算法的时间复杂度。

1) 交换i和j的内容

Temp=i;
i=j;
j=temp;

以上三条单个语句的频度均为1，该程序段的执行时间是一个与问题规模n无关的常数。算法的时间复杂度为常数阶，记作T(n)=O(1)。

注意：如果算法的执行时间不随着问题规模n的增加而增长，即使算法中有上千条语句，其执行时间也不过是一个较大的常数。此类算法的时间复杂度是O(1)。

2) 变量计数之一

(1) x=0;y=0;
(2) for(k=1;k<=n;k++)
(3)     x++;
(4) for(i=1;i<=n;i++)
(5)     for(j=1;j<=n;j++)
(6)     y++;

一般情况下，对步进循环语句只需考虑循环体中语句的执行次数，忽略该语句中步长加1、终值判别、控制转移等成分。因此，以上程序段中频度最大的语句是(6)，其频度为f(n)=n²，所以该程序段的时间复杂度为T(n)=O(n^2)。

当有若干个循环语句时，算法的时间复杂度是由嵌套层数最多的循环语句中最内层语句的频度f(n)决定的。

3) 变量计数之二

(1) x=1;
(2) for(i=1;i<=n;i++)
(3)     for(j=1;j<=i;j++)
(4)         for(k=1;k<=j;k++)
(5)             x++;

该程序段中频度最大的语句是(5)，内循环的执行次数虽然与问题规模n没有直接关系，但是却与外层循环的变量取值有关，而最外层循环的次数直接与n有关，因此可以从内层循环向外层分析语句(5)的执行次数：

则该程序段的时间复杂度为T(n)=O(n³/6+低次项)=O(n^3)。

（4）算法的时间复杂度不仅仅依赖于问题的规模，还与输入实例的初始状态有关。

在数值A[0..n-1]中查找给定值K的算法大致如下：

(1) i=n-1;
(2)     while(i>=0&&(A[i]!=k))
(3)         i--;
(4)         return i;

此算法中的语句(3)的频度不仅与问题规模n有关，还与输入实例中A的各元素取值及K的取值有关:

①若A中没有与K相等的元素，则语句(3)的频度f(n)=n；

②若A的最后一个元素等于K,则语句(3)的频度f(n)是常数0。

2 空间复杂度

2.1 空间复杂度简介

与时间复杂度类似，空间复杂度(Space Complexity)是指算法在计算机内执行时所需存储空间的度量。记作:

S(n)=O(f(n))

算法执行期间所需要的存储空间包括3个部分：

• 算法程序所占的空间；
• 输入的初始数据所占的存储空间；
• 算法执行过程中所需要的额外空间。

在许多实际问题中，为了减少算法所占的存储空间，通常采用压缩存储技术。

算法的输入输出数据所占用的存储空间是由要解决的问题决定的，是通过参数表由调用函数传递而来的，它不随本算法的不同而改变。存储算法本身所占用的存储空间与算法书写的长短成正比，要压缩这方面的存储空间，就必须编写出较短的算法。算法在运行过程中临时占用的存储空间随算法的不同而异，有的算法只需要占用少量的临时工作单元，而且不随问题规模的大小而改变，我们称这种算法是“就地"进行的，是节省存储的算法，有的算法需要占用的临时工作单元数与解决问题的规模n有关，它随着n的增大而增大，当n较大时，将占用较多的存储单元，例如快速排序和归并排序算法就属于这种情况。

2.2 空间复杂度的分析

分析一个算法所占用的存储空间要从各方面综合考虑。如对于递归算法来说，一般都比较简短，算法本身所占用的存储空间较少，但运行时需要一个附加堆栈，从而占用较多的临时工作单元；若写成非递归算法，一般可能比较长，算法本身占用的存储空间较多，但运行时将可能需要较少的存储单元。

一个算法的空间复杂度只考虑在运行过程中为局部变量分配的存储空间的大小，它包括为参数表中形参变量分配的存储空间和为在函数体中定义的局部变量分配的存储空间两个部分。若一个算法为递归算法，其空间复杂度为递归所使用的堆栈空间的大小，它等于一次调用所分配的临时存储空间的大小乘以被调用的次数(即为递归调用的次数加1，这个1表示开始进行的一次非递归调用)。

算法的空间复杂度一般也以数量级的形式给出。如当一个算法的空间复杂度为一个常量，即不随被处理数据量n的大小而改变时，可表示为O(1)；当一个算法的空间复杂度与以2为底的n的对数成正比时，可表示为O(log2n)；当一个算法的空间复杂度与n成线性比例关系时，可表示为O(n).若形参为数组，则只需要为它分配一个存储由实参传送来的一个地址指针的空间，即一个机器字长空间；若形参为引用方式，则也只需要为其分配存储一个地址的空间，用它来存储对应实参变量的地址，以便由系统自动引用实参变量。

3 时间空间复杂度

对于一个算法，其时间复杂度和空间复杂度往往是相互影响的。当追求一个较好的时间复杂度时，可能会使空间复杂度的性能变差，即可能导致占用较多的存储空间；反之，当追求一个较好的空间复杂度时，可能会使时间复杂度的性能变差，即可能导致占用较长的运行时间。另外，算法的所有性能之间都存在着或多或少的相互影响。因此，当设计一个算法(特别是大型算法)时，要综合考虑算法的各项性能，算法的使用频率，算法处理的数据量的大小，算法描述语言的特性，算法运行的机器系统环境等各方面因素，才能够设计出比较好的算法。算法的时间复杂度和空间复杂度合称为算法的复杂度。

二、说明分治与递归的思想？

1 分治算法

分治算法（Divide-and-conquer algorithm）的基本思想是将一个规模为N的问题分解为K个规模较小的子问题，这些子问题相互独立且与原问题性质相同。求出子问题的解，就可得到原问题的解。即一种分目标完成程序算法，简单问题可用二分法完成。

当我们求解某些问题时，由于这些问题要处理的数据相当多，或求解过程相当复杂，使得直接求解法在时间上相当长，或者根本无法直接求出。对于这类问题，我们往往先把它分解成几个子问题，找到求出这几个子问题的解法后，再找到合适的方法，把它们组合成求整个问题的解法。如果这些子问题还较大，难以解决，可以再把它们分成几个更小的子问题，以此类推，直至可以直接求出解为止。这就是分治策略的基本思想。

2 递归算法

递归算法（Recursion algorithm）在计算机科学中是指一种通过重复将问题分解为同类的子问题而解决问题的方法。递归式方法可以被用于解决很多的计算机科学问题，因此它是计算机科学中十分重要的一个概念。绝大多数编程语言支持函数的自调用，在这些语言中函数可以通过调用自身来进行递归。计算理论可以证明递归的作用可以完全取代循环，因此在很多函数编程语言（如Scheme）中习惯用递归来实现循环。

在数学与计算机科学中，递归是指在函数的定义中使用函数自身的方法。实际上，递归，顾名思义，其包含了两个意思：递 和 归，这正是递归思想的精华所在。

递归就是有去（递去）有回（归来），“有去”是指：递归问题必须可以分解为若干个规模较小，与原问题形式相同的子问题，这些子问题可以用相同的解题思路来解决，就像上面例子中的钥匙可以打开后面所有门上的锁样；“有回”是指 : 这些问题的演化过程是一个从大到小，由近及远的过程，并且会有一个明确的终点(临界点)，一旦到达了这个临界点，就不用再往更小、更远的地方走下去。最后，从这个临界点开始，原路返回到原点，原问题解决。

递归算法常用于解决以下几类问题

• 数据的定义是按递归定义的。如Fibonacci函数。
• 问题解法按递归算法实现。如Hanoi问题。
• 数据的结构形式是按递归定义的。如二叉树、广义表等。

三、列举几个常用的排序/遍历的算法，写出其用到哪些思想，它的时间复杂度是多少？列举2-3个即可！

1 冒泡排序

1.1 原理

​ 1）比较相邻的元素。如果第一个比第二个大，就交换他们两个。

​ 2）对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。

​ 3）针对所有的元素重复以上的步骤，除了最后一个。

​ 4）持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

冒泡的过程只涉及相邻数据的交换操作，属于原地排序算法

以Python代码为例展示冒泡排序的算法过程：

def bubble_sort(nums):
    for i in range(len(nums) - 1): 
        for j in range(len(nums) - i - 1):
            if nums[j] > nums[j + 1]:
                nums[j], nums[j + 1] = nums[j + 1], nums[j]
    return nums

1.2 时间复杂度

若数据的初始状态是正序的，一趟扫描即可完成排序。所需的关键字比较次数 和记录移动次数 均达到最小值： n-1，所以，冒泡排序最好的时间复杂度为O(n) 。

若数据的初始状态是反序的，需要进行n-1趟排序。每趟排序要进行n-i次关键字的比较(1≤i≤n-1)。在这种情况下，比较次数达到最大值： ，所以，冒泡排序最坏的时间复杂度为O(n²) 。

综上，因此冒泡排序总的平均时间复杂度为O(n²) 。

2 快速排序

2.1 原理

快速排序算法通过多次比较和交换来实现排序，其排序流程如下：

​ 1) 首先设定一个分界值，通过该分界值将数组分成左右两部分。

​ 2) 将大于或等于分界值的数据集中到数组右边，小于分界值的数据集中到数组的左边。此时，左边部分中各元素都小于或等于分界值，而右边部分中各元素都大于或等于分界值。

​ 3) 然后，左边和右边的数据可以独立排序。对于左侧的数组数据，又可以取一个分界值，将该部分数据分成左右两部分，同样在左边放置较小值，右边放置较大值。右侧的数组数据也可以做类似处理。

​ 4) 重复上述过程，可以看出，这是一个递归定义。通过递归将左侧部分排好序后，再递归排好右侧部分的顺序。当左、右两个部分各数据排序完成后，整个数组的排序也就完成了。

快速排序算法用到了递归的思想。

以Python代码为例展示快速排序的算法过程：

def quick_sort(data):     
    if len(data) >= 2:       
        mid = data[len(data)//2]        
        left, right = [], []       
        data.remove(mid)        
        for num in data:            
            if num >= mid:                
                right.append(num)            
            else:                
                left.append(num)        
        return quick_sort(left) + [mid] + quick_sort(right)    
    else:        
        return data

2.2 时间复杂度

快速排序最优的情况下时间复杂度为：O( nlog2n )

快速排序最坏的情况下时间复杂度：O( n^2 )

快速排序的平均时间复杂度也是：O(nlog2n)

四、系统比较Sanger测序和新一代高通量测序从样本制备，到测序流程，再到后续分析的异同，及其优缺点。

1 样品制备

• Sanger测序

  将随机DNA片段的大量拷贝克隆岛质粒并转化大肠杆菌（随机从头测序），或使用引物对目标片段惊醒PCR扩增。测序样本一般是载体质粒、PCR产物、提的基因组，还可以是菌液、沉菌等。

• 新一代高通量测序

  首先随机切割样品基因组，获得大量DNA片段，之后对DNA片段进行末端修复、加A、加接头及纯化，然后进行PCR扩增反应。

2 测序流程

• Sanger测序

  1）聚合反应

  向样本中加入包含四种带荧光标记的ddNTP、四种dNTP、DNA聚合酶、镁离子、ph缓冲液等试剂，进行聚合反应。和普通PCR相比，测序PCR，使用的引物为单向，且对模板的浓度及纯度要求相当高。

  2）纯化产物

  聚合反应会在不同的位置终止，之后过滤混合物，去除ddNTP等其他杂质，只留下长短不一的DNA片段。

  3）毛细管电泳
  将纯化后的聚合反应产物用毛细管电泳法的高分辨率变性凝胶电泳分离出大小不同的片段，凝胶处理后可用X-光胶片放射自显影或非同位素标记进行检测。荧光标记的DNA链按从小到大的顺序被毛细管电泳分离，激光诱导的荧光终止剂被检测器识别，直接阅读DNA的核苷酸序列。

• 新一代高通量测序

  1）线性化

  经过样品制备过程的PCR扩增反应步骤后，所有的模板首先被线性化处理而形成单链模板。

  2）引物结合

  固相载体上连接着许多与接头相互补的引物，退火后，单链线性DNA片段即能结合到固相载体上。

  3）桥式PCR

  与模板结合的引物附近存在着与模板另一端接头相互补的引物，因此经过桥式PCR形成大量的成蔟的单链DNA。加入ddNTP，阻断断发生聚合反应的引物，以免影响后续进程。

  4）聚合反应

  加入测序引物，根据变合成测序的原理，在聚合酶的指导下，带有荧光基团的脱氧核苷酸结合到模板上，并释放出一个荧光信号。每一轮反应都会释放出一个荧光信号，并被荧光信号采集系统所记录下来。每种脱氧核苷酸所携带的荧光基团不同，因此，根据不同的荧光信号可以识别出对应位点的序列信息。

3 后续分析

• Sanger测序

  1）引物之后的20bp甚至50bp之内的序列是不准确的，这主要是因为残存的染料单体造成的干扰峰所致，该干扰峰和正常序列峰重叠在一起；另外，测序电泳开始阶段电压有一个稳定期。

  2）序列末端容易产生N值，峰图较杂。由于测序反应的信号是逐渐减弱的，所以序列末端的信号会很弱，峰图自然就会杂乱，加上测序胶的分辨率问题，如果碱基分不开，就会产生N值。

  3）每个测序反应会提供两个结果，一个是序列，一个是峰图；序列可以用Word，DNAStar、写字板等软件打开，峰图可以用Chromas软件及其他综合性软件打开。

• 新一代高通量测序

  经过60-120轮的聚合反应，荧光信号采集系统采集每一循环产生的荧光信号，并形成一幅具有不同时相的荧光图片。荧光图片上的每一个亮点即代表着每个基因簇，通过读取不同时相的对应位置荧光信号的种类即可读出模板的碱基序列。

4 优缺点

• Sanger测序

  1）优点

  最大优点在于读长很高，可达1000bp；准确性较高，而且成本相对很低。富含G-C的区域也不会影响测序效果。

  2）缺点

  测序试剂昂贵、处理比较长，DNA模板的组成或二级结构有时引起DNA聚合酶不正常终止

• 新一代高通量测序

  1）优点

  最显著的优点是通量高，可以在数百万个点上同时阅读测序，把平行处理的思想用到极致，因此也称之为大规模平行测序，大大降低了测序成本的；

  同时，还大幅提高了测序速度，并且保持了高准确性

  2）缺点

  缺点是读长较短（200bp-500bp）、不适于de novo sequence、产生的数据文件过大等。