第一章-算法概述

1. 递归算法必须具备的两个条件是边界条件或停止条件和递推方程或递归方程
2. 冒泡排序时间复杂度是___，堆排序时间复杂度是___。 $O(n^2)$,$O(nlogn)$
3. 斐波那契数列的第1项为1，第2项为2，以后每一项等于前面两项之和，则第6项为13
4. 算法分析主要是分析算法的性能，包括时间复杂度和空间复杂度
5. 请求解递归式：n>1时，T(n)=2T(n/2)+n,否则T（n）=1，则其θ形式，T（n）=θ(nlogn)
6. 以下递归程序fun(5,0)输出的第一个元素是1，求解过程中最大层次为4

算法分析基础上机题目

1.旅行商问题

【问题描述】

假设有一个旅行商人要拜访n个城市，他必须选择所要走的路径，路径的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值。

【输入形式】

城市数目，以及城市之间的距离

【输出形式】

所有路径之中的最小值

【样例输入】

4

0,10,15,20

10,0,35,25

15,35,0,30