第一章：算法引论
1，什么是算法？算法有哪些基本特征？请指出算法同程序的相同点与不同点。
答：算法是解决问题的方法或过程，是满足以下四个性质的指令序列
1）输入：有 0 个以上的输入 2）输出：至少有 1 个输出
3）确定性：指令清晰、无歧义 4）有限性：指令执行次数有限，时间有限
5）可行性：
算法和程序的相同点：两者都具有输入、输出和确定性的特征 不同点：程序是算法用某种程序语言的具体实现，程序不满足算法具有的有限性性质 请描述算法设计的一般过程。
2，请描述算法设计的一般过程。
答：算法设计的一般过程是 1）提出问题 2）确定数学模型 3）明确目的、条件和约束关系 4）设计求解步骤 5）结果评估与分析 如果在第 5 步的分析中对算法时间、空间复杂度或结果不满意，可以返回第 1 步或第 4 步进一步迭代，直至找到满意的算法。
3，什么是算法复杂性？它主要有哪两个方面构成？
答：算法复杂性是算法运行时所需要的计算机资源的量，它包括两个方面：时间复杂性（需 要时间资源的量）和空间复杂性（需要空间资源的量） 。
4，时间复杂性分析主要分哪三种情况，哪种情况的可操作性最好，最具有实际价值？
答：时间复杂性分为 3 种情况，最好情况、平均情况、最坏情况，可操作性最好，最具有实 际价值的是最坏情况下的时间复杂性。
最坏情况时间复杂性是规模为n的所有输入中，基本运算执行次数为最多的时间复杂性。
平均情况时间复杂性是规模为n的所有输入的算法时间复杂度的平均值 （一般均假设每种输入情况以等概率出现）。
5，表示渐进时间复杂性的三个记号的具体定义是什么？
答：1. T(n)= O(f(n))：若存在c > 0，和正整数n0≥1，使得当n≥n0时， 总有 T(n)≤c*f(n)。 （给出了算法时间复杂度的上界，不可能比c*f(n)更大）
2. T(n)=Ω(f(n))：若存在c > 0，和正整数n0≥1，使得当n≥n0时， 存在无穷多个n ，使得T(n)≥c*f(n)成立。（给出了算法时间复杂度的下界，复杂度不可能比c*f(n)更小）
3. T(n)= Θ(f(n))：若存在c1,c2>0，和正整数n0≥1，使得当n≥n0时， 总有 T(n)≤c1*f(n)，且有无穷多个n，使得T(n)≥c2*f(n)成立， 即：T(n)= O(f(n))与T(n)=Ω(f(n))都成立。（既给出了算法时间复杂度的上界，也给出了下界）。
6，算法研究有哪几个主要步骤？主要从哪几个方面评价算法？
答：算法研究的主要步骤是1)设计2）表示 3）确认，合法输入和不合法输入的处理 4）分析 5）测试。
评价算法的标准有1）正确性 2）健壮性 3）简单性 4）高效性 5）最优性
7，各种增长函数的含义。
答：
| 数学表达式
|
相对增长率
|
| T(N)=O(g(N))
|
T(N)的增长 ≤ g(N)的增长 |
| T(N)=Ω(g(N))
|
T(N)的增长 ≥ g(N)的增长 |
| T(N)=θ(g(N))
|
T(N)的增长 ＝ g(N)的增长 |
| T(N)=o(g(N))
|
T(N)的增长 ＜ g(N)的增长 |
O(1)<O(logn)<O(n)<O(nlogn)<O(n2)<O(n3)<O(an)<O(n!)<O(nn)。
例题：
1，
2，
3，
4，
5，
6，如果算法A由三个步骤组成，其中第一步的时间复杂性为O(n2)，第二步的时间复杂性为O(nlogn)，第三步的时间复杂性为O(n)，请问算法A的时间复杂性是多少？
答：O(n2)
7, 解决某问题有三种算法，复杂性分别为1000N，10N2， 2N ，在一台机器上可处理问题的规模分别为S1 ， S2 ， S3 。若机器速度提高到原来的10倍，问在同样时间内可处理问题的大小如何？
答：
复杂性 原来处理问题规模 速度提高以后
1000N S1 10S1
10N2 S2 3.16S2
2N S3 S3 +log10≈ S3 +3.32
8，问题P的算法复杂度为T(n)=n3（毫秒），现改善为T(n)=n2（毫秒）。问原来运行一小时的问题实例，现在要运行多少时间？
答：
设实例大小为n，
则 n3=3600*1000
n=153.3
∴ 现在需要时间t=153.32毫秒≈ 23.5秒
9，
1），f(n) = 2n + 3 = O(n)
当n≥3时，2n+3≤3n，所以，可选c = 3，n0 = 3。对于n≥n0，f(n) = 2n + 3≤3n，所以，f(n) = O(n)，即2n + 3O(n)。这意味着，当n≥3时，程序2-1的程序步不会超过3n，2n + 3 = O(n)。
2），f(n) = 10n2 + 4n + 2 = O(n2)
对于n≥2时，有10n2 + 4n + 2≤10n2 + 5n，并且当n≥5时，5n≤n2，因此，可选c = 11, n0 = 5；对于n≥n0，f(n) = 10n2 + 4n + 2≤11n2，所以f(n) = O(n2)。
3），10n2 + 9 O(n)
使用反证法，假定存在c和n0，使得对于n≥n0，10n2 + 9≤cn始终成立，那么有10n + 9/n≤c，即n≤c/10 9/(10n)总成立。但此不等式不可能总成立，取n = c/10 + 1时，该不等式便不再成立。
本文转自 梦朝思夕 51CTO博客，原文链接:http://blog.51cto.com/qiangmzsx/802712
