算法的基本概念

对特定问题求解步骤的一种描述，它是指令的有限序列，其中的每条指令表示一个或多个操作。

根据以上定义，可以知道，算法一定是可以解决特定问题的，其次，它是有限的，然后，每一个指令都表示特定的操作。于是可以知道算法的五个特性：

有穷性：一个算法必须在执行有穷步之后结束，且每一步都必须在有穷时间内完成。如果有类似无限循环的语句，那么就不能称之为算法。
可行性：一个算法是可行的，即算法中描述的操作都是可以通过已经实现的基本运算执行有限次来实现的。每一步操作都是可以实现的才能称之为算法。
确定性：算法中每条指令、每条语句必须有确切的含义，相同的输入必须得出到相同的输出，不能产生二义性。
输入：一个算法必须有零个或多个输入。
输出：一个算法必须有一个或多个输出。

算法为什么是有穷的？在操作系统中使用了很多无穷的代码语句，它们也是非常有用的，它们不是算法，那它们又是什么？

对此，引入一个程序的概念，什么是算法，什么又是程序

根据上面的算法的定义，可以知道，算法是解决问题的一种方法或一个过程，例如如何将输入转换成输出。一个问题可以有很多不同的算法。而程序是某种程序设计语言对算法的具体实现。我们可以用 C 语言来编写，也可以用 Python 语言来编写，只要是在计算机内部运行的程序设计语言都可以。这是对算法和程序的简单描述。我们发现，算法更像一个解决问题的 “指导者”，而程序更像一个具体实现的 “实施者”，可以利用算法来指导程序的编写和实施。

算法和程序主要有三方面的区别：

有穷性：算法必须是有穷的，程序可以是无穷的，所以在操作系统中，那些很有用的，但又无限循环的，可以 称之为程序。
正确性：算法必须是正确的，程序可以是错误的。设计出的算法必须正确的来解决问题，而程序可以编写错误然后进行修改。
描述方法：算法可以用伪代码、程序语言、自然语言、程序框图等描述，程序只能用程序设计语言编写并可以运行。

算法效率的度量

如何设计一个 "好" 的算法？

首先一个好的算法必须具有正确性，应该能够正确的解决问题。算法是一个 “指挥者”，如果一个 “指挥者” 不能正确的指导 “实施者” 去实施，那么它一定不是一个好的算法。

第二个是可读性。算法应具有良好的可读性，以帮助人们理解。在人们修改阅读算法时，人们应能够快速的理解掌握该算法。

第三个是健壮性。健壮性是指在输入非法数据时，算法能适应的做出反应或进行处理。

最后一个是效率与存储量需求。效率是指算法执行时间，存储量需求是指算法执行过程中所需最大存储空间。这是最常用的用来考量一个好的算法的标准。也就是时间复杂度与空间复杂度。

时间复杂度

在学习时间复杂度之前，先掌握两个概念：语句的频度、T(n)

语句频度：该条语句可能重复执行的次数

T(n)：所有语句的频度之和，其中 n 为问题的规模

int sum = 0;  
for(int i=1; i<=n; i++)  
    sum += i;  

第一句是初始化 su...

课后习题

【2019年真题】设n是描述问题规模的非负整数，下列程序段的时间复杂度是

x = 0;  
while (n >= (x + l) * (x + l))  
x = x + l;  

A. O(log₂n)      B. O(n^1/2)       C. O(n)       D. O(n²)

参考答案：B

【2017年真题】下列函数的时间复杂度是

int func(int n) {  
    int i=0, sum=0;  
    while (sum < n) sum += ++i;  
    return i;  
}  

A.O(log₂n)        B.O(n^1/2)        C.O(n)        D.O(nlog₂n)

参考答案：B

【2014年真题】下列程序段的时间复杂度是（）。

count = 0;  
for (k = 1; k <= n; k *= 2)  
    for (j = 1; j <= n; j++)  
        count++;  

A．O(log₂n)        B．O(n)    C．O(nlog₂n)    D．O(n²)

参考答案：C
答案解析：内层循环条件 j<=n 与外层循环的变量无关，每次循环 j 自增 1，每次内层循环都执行 n 次。外层循环条件为 k<=n，增量定义为 k*=2，可知循环次数为 2k <=n，即 k<=log₂n。
所以内层循环的时间复杂度是 O(n)，外层循环的时间复杂度是 O(log₂n)。对于嵌套循环，根 
据乘法规则可知，该段程序的时间复杂度 T(n)=T1(n)*T2(n)=O(n)*O(log₂n)=O(nlog₂n)。 

【2013年真题】已知两个长度分别为 m 和 n 的升序链表，若将它们合并为一个长度为 m+n 的降序链表，则最坏情况下的时间复杂度是（）
A. O(n)         B. O(m * n)     C. O(min(m, n))         D. O(max(m, n))

参考答案：D
答案解析：m、n 是两个升序链表，长度分别为 m 和 n。在合并过程中，最坏的情况是两个链表中的元素依次进行比较，比较的次数最少是 m 和 n 中的最小值。 

【2012年真题】求整数 n(n≥0)阶乘的算法如下，其时间复杂度是（）

int fact(int n){  
    if (n <= 1) return 1;  
    return n * fact(n - 1);  
}  

A. O(log₂n) 
B. O(n) 
C. O(nlog₂n) 
D. O(n²)

参考答案：B
答案解析：考查时间复杂度的计算。 
该程序中使用了递归运算。本题中递归的边界条件是 n<=1，每调用一次 fact()，传入该层 fact()的参 数值减 1（注意不是 n 减 1），因此执行频率最高的语句是 return n*fact(n-1)，一共执行了 n-1 次，而每一层 fact(i)运算只包含一次乘法。如果采用递归式来表示时间复杂度，则：

时间复杂度为 O(n)。 

【2011年真题】设 n 是描述问题规模的非负整数，下面程序片段的时间复杂度是（）

x = 2;  
while (x < n/2）  
x = 2 * x;  

A．O(log₂n) 
B．O(n) 
C．O(nlog₂n)
D．O(n²) 

解答：A。程序中，执行频率最高的语句为“x=2*x”。设该语句执行了t次，则2 t+1=n/2， 
故t=log₂(n/2)-1=log₂n-2= O(log₂n)。