第1章算法及基础知识(改).pptVIP

例1.1 T(n)＝3n-1 【解答】 当n≥1时，3n-1≤3n＝O(n) 当n≥1时，3n-1≥3n-n＝2n＝Ω(n) 当n≥1时，3n≥3n-1≥2n，则3n-1＝Θ(n) 例1.2 T(n)＝5n2＋8n＋1 【解答】当n≥1时，5n2＋8n＋1≤5n2＋8n＋n＝5n2＋9n≤5n2＋9n2≤14n2＝O(n2) 当n≥1时，5n2＋8n＋1≥5n2＝Ω(n2) 当n≥1时，14n2≥5n2＋8n＋1≥5n2，则5n2＋8n＋1＝Θ(n2) 渐进符号——运行时间的精确阶 定理1.1 若T(n)=amnm +am-1nm-1 + … +a1n+a0（am0），则有T(n)=O(nm)，且T(n)=Ω(nm)，因此，有T(n)=Θ(nm)。 算法时间复杂度分析——定理 空间复杂度 算法所占用的存储空间包括 算法自身 输入、输出 辅助空间(本书的空间复杂性只考虑辅助空间) 空间复杂度S(n)=O(f(n))，以最坏情况来分析 例：插入法升序排序 void insert_sort(int n,int s[]) { int a,i,j; for (i=1;in;i++) { a=s[i]; j=i-1; while(j=0 s[j]a) { s[j+1]=s[j]; j--; } s[j+1]=a; } } 辅助空间为a,i,j，没有在基本语句中产生新的辅助变量，因此S(n)=O(1) 算法的运行时间T(n)建立的依据 非递归算法 （a）选择某种能够用来衡量算法运行时间的依据(找出对算法运行时间贡献最大的原操作语句作为基本语句来进行衡量)； （b）依照该依据求出运行时间T(n)的表达式； （c）采用渐进符号表示T(n)； （d）获得算法的渐进时间复杂性，进行进一步的比较和分析。 举[例1-4]、[例1-5]进行说明 算法的运行时间T(n)建立的依据 例1-4 int arrayMax(int a[n]) { int max=a[0]; for(int i=1;in;i++) if(a[i]max) max=a[i]; return max; } T(n)=n-1=O(n) 算法的运行时间T(n)建立的依据 例1-5 int find(int a[n],int K) { for(int i=0;in;i++) if(a[i]==K) break; return i; } T(n)=O((n+1)/2)=O(n) 递归 子程序（或函数）直接调用自己或通过一系列调用语句间接调用自已，称为递归。直接或间接调用自身的算法称为递归算法 。 采用递归算法来求解问题的一般步骤： 分析问题，寻找递归关系 找出停止条件 构建函数体 n的阶乘 停止条件 递归关系 停止条件与递归关系是递归函数的两个要素，递归函数只有具备了这两个要素，才能在有限次计算后得出结果。 n的阶乘 long long fun(int n) { if(n0) { printf(Illegal number!\n); break; } else if(n==0) return 1; else return n*fun(n-1) } 排列问题 问题描述 n个元素，它们的编号为1,2,…,n，排列问题的目的是生成这n个元素的全排列。 算法设计思路 将规模为n的排列问题转化为规模为n-1的排列问题。 将规模为n-1的排列问题转化为规模为n-2的排列问题 将问题规模一级一级降至1，1个元素的排列是它本身，此时到达递推的停止条件。数组中的元素即为1个排列，然后进行回归依次得到其它的排列。 排列问题 具体设计过程 将规模为n的排列问题转化为规模为n-1的排列问题 数组的首元素定义为1，即排列的第一个元素为1，还需要生成后面n-1个元素的全排列。 将数组的第一个元素和第二个元素互换，使得数组的首元素为2，即排列的第一个元素为2，还需要生成后面n-1个元素的全排列。 以此类推........ 将数组的第一个元素和第n个元素互换，使得数组的首元素为n,即排列的第一个元素为n，还需要生成后面n-1个元素的全排列。 将规模为n-1的全排列的问题转化为规模为n-2的问题。 1-1 : 数组的第二个元素为2，即排列的第二个元素为2，还需要生成后面n-2个元素的全排列。 1-2 : 数组的第二个元素和第三个元素互换，使得数组的第二个