1． 算法的性质 输入：有零个或多个外部量作为算法的输入。 输出：算法产生至少一个量作为输出。 确定性：组成算法的每条指令清晰、无歧义。 有限性：算法中每条指令的执行次数有限，执行每条指令的时间也有限。（有效性即可执行性） 2．递归方程的两个要素 边界条件、递归方程 3．常 见 渐 近 阶 的 顺 序 排 列 4．什 么是算法复杂性 包括时间复杂度和空间复杂度。时间复杂度指程序执行时所用的时间；空间复杂度指算法占用的空间（两种占用：存储程序和输入数据的空间、存储中间结果或操作单元所占用空间——额外空间） 5．回溯法中的解空间结构 子集树、排列数 6 ．分治法的 基本思想及步骤 分治法的基本思想是将一个规模为n 的问题分解为k 个规模较小的子问题，这些子问题互相独立且与原问题相同。递归地解这些子问题，然后将各个子问题的解合并得到原问题的解。 7．二分搜索的概念 二分搜索是将 n 个元素分成个数大致相同的两半，取 a[n/2]与 x 做比较。如果x=a[n/2],则找到 x，算法终止；如果x
a[n/2],则只要在数组a 的右半部继续搜索 x。P16 8． Strassen 矩 阵 乘 法 P18 标 记 处 9．备 忘 录 法 与动态规划法 的异同 即去除冗余计算。 10．整数背包：动态规划、回溯 （时间复杂度，算法思想） P77 算法复杂度分析： 改进后算法的计算时间复杂性为O(2n)。当所给物品的重量wi(1≤i≤n)是整数时，|p[i]|≤c+1，(1≤i≤n)。在这种情况下，改进后算法的计算时间复杂性为O(min{nc,2n} )。 P158（0-1 背包问题回溯法思想，时间复杂度） 11．部分背包：贪心 #include #define MAXSIZE 100 //假设物体总数 #define M 20 //背包的载荷能力 //算法核心，贪心算法 void GREEDY(float w[], float x[], int sortResult[], int n) {float cu = M; int i = 0; int temp = 0; for (i = 0; i < n; i++)//准备输出结果 {x[i] = 0;} for (i = 0; i < n; i++) {temp = sortResult[i];//得到取物体的顺序 if (w[temp] > cu) {break;} x[temp] = 1;//若合适则取出 cu -= w[temp];//将容量相应的改变} if (i <= n)//使背包充满 { x[temp] = cu / w[temp];} return;} void sort(float tempArray[], int sortResult[], int n) {int i = 0,...
