概述
算法·Algorithm练习题思考题
算法·Algorithm
算法定义 有穷性/终止性、确定性、可行性、输入、输出问题定义 输入和输出的关系计算复杂性理论 固有复杂性，上界复杂性，下界复杂性，平均复杂性，复杂性问题分类：P=NP？，抽象复杂性研究算法正确性分析 对于每一个输入是否都最终停止？且是否产生正确的输出？ 不停止或产生不正确结果，都是不正确算法 注：近似算法对所有输入都停止，但产生近似正确的解或产生不多的不正确解算法复杂性分析 目的：预测算法对不同输入所需资源量 复杂性测度：时间、空间、I/O，是输入大小的函数 用途：为一个求解问题 选择最佳算法和最佳设备 数学基础：离散数学、组合数学、概率论、代数 复杂性分析的度量：输入大小、时间复杂性（是输入大小的函数）、空间复杂性、最坏复杂性（max）、最小复杂性（min）、平均复杂性（y∈Input，y作为算法A的输入出现的概率是Py，A的平均复杂性是
Γ
(
z
)
=
Σ
P
y
∗
c
o
m
p
l
e
x
i
t
y
(
s
i
z
e
(
y
)
)
\Gamma(z) = Σ Py*complexity(size(y))
Γ(z)=ΣPy∗complexity(size(y))）算法设计模式 暴力搜索，分治法，图搜索与枚举（分支界限、回溯），随机化方法算法实现方法 递归与迭代，顺序、并行与分布式，确定性与非确定性，近似求解与精确求解，量子算法最优化算法设计方法 线性规划，动态规划，贪心法，启发式方法
练习题
(1). 用伪代码写出求整数最大公因子的欧几里得算法。
1.输入两个数m,n 2.if(m>n)，求余数m%n 3.若余数不为0，用n替代m，用余数替代n => 重复2 4.若余数为0，则n就是最大公约数
例如，求81和21的最大公约数： 81/21=3…18 21/18=1…3 18/3=6…0 ∴最大公约数为3
(2). 考虑如下伪代码 F(n) 1 if n=1 2 then return 1 3 else return n*F(n-1) 请说明F(n)的功能
斐波那契数列计算乘积 例如，n=5时： return 5xF(4)=5x4xF(3)=…=5x4x3x2x1=120
(3). 时间复杂度是否是衡量一个算法性能的主要标准，为什么？
衡量一个算法性能原则上无标准。【时间、空间、IO、并行性】复杂度；内存算法中【时间、空间】占主导
(4). 包含死循环的程序是不是算法，为什么？
不是。有穷性？
(5). 是否可以通过提高算法的时间复杂性来降低其空间复杂性？
时空互换：时间复杂度<->空间复杂度 动态规划：空间换时间【台阶问题的动态规划】
思考题
(1).在信息产业中算法扮演什么角色？
算法是计算机科学基础的重要主题（啥玩意儿…）
