算法课件第1章绪论.pptVIP

* a相当于f(n),b相当于g(n) * 上面的运算可以理解为两个算法的串行执行和嵌套执行 * 举例: （1）N=15，a=2,b=2；（2） a=15,b=4 * e＝1+1/1!+1/2!+1/3!+…＝ 2.718281828459….. * 毫秒 * Ti是当in时，第i次进入for循环后，假设while循环执行的次数；插值排序就是差扑克 ?2.1 * a[i]是降序数组，每个值在插入前都要同前面所有的值比一遍，O(n) = Tmax(n) = Ω(n) * 对于输入数据a[i]=n-i,i=0,1,…,n-1，算法insertion_sort 达到其最坏情形。因此， 由此可见，Tmax(n)= ?(n2) * 问题的计算时间下界为?(f(n))，则计算时间复杂性为O(f(n))的算法是最优算法。 例如，排序问题的计算时间下界为?(nlogn)，计算时间复杂性为O(nlogn)的排序算法是最优算法。 堆排序算法是最优算法。 最优算法 * 算法在计算机科学中的地位 算法的概念 算法分析 掌握算法的计算复杂性概念 掌握算法渐近复杂性的数学表述 总结 * * * * * 计算机科学是一种创造性思维活动，其教育必须面向设计 算法是任何定义好了的计算程式，它取某些值或值得集合作为输入，并产生某些值得集合作为输出。 * * 最早的算法是欧几里德的“求最大公因子算法” * * * * * * * * * * * * * 2.2 Size(I),其中的I是输入 * 2.2 Size(I),其中的I是输入 * 2.2 Size(I),其中的I是输入 * 2.2 Size(I),其中的I是输入 * 3.1 * 3.2 * 3.2 * 3.2 * 3.2 * 3.2 * 插入排序的时间复杂性（最好） Insertion-sort(A) 1. for j=2 to n do cost times 2. key?A?j?; c1 n-1 3. i?j-1; c2 n-1 4. while i0 and A?i?key do c3 n-1 5. A?i+1??A?i?; c4 0 6. i?i-1; c5 0 7. A?i+1??key; c6 n-1 * 插入排序的时间复杂性 * T(n) ?? , as n?? ; (T(n) - t(n) )/ T(n) ?0 ，as n??;t(n)是T(n)的渐近性态，为算法的渐近复杂性。 在数学上， t(n)是T(n)的渐近表达式，是T(n)略去低阶项留下的主项。它比T(n) 简单。 算法的渐近复杂性 * 对于正值函数f(n) ? 0和g(n) ? 0，如果存在正常数c和n0使得对所有n? n0有：f(n) ? cg(n) ，则称f(n) 是g(n)的低阶函数或g(n)是f(n)的渐近上界，记为f(n)=O(g(n)) 渐近分析的记号 —— 渐进上界 O * 对于正值函数f(n) 和g(n) ，如果存在正常数c和n0使得对所有n? n0有：f(n) ? cg(n) ，则称f(n)是g(n)的高阶函数或g(n)是f(n)的渐近下界，记为 f(n)=?(g(n)) 渐近分析的记号 —— 渐进下界 ? * 对于正值函数f(n) 和g(n) ，如果存在正常数c1，c2和n0使得对所有n? n0有： c1g(n) ? f(n) ?c2g(n) ，则称f(n)是g(n)的同阶函数，记为f(n)=? (g(n)) f(n)=?(g(n)) iff f(n)=O(g(n)) ? f(n)=?(g(n)) 渐近分析的记号 ——同阶函数 ? * 正值函数f(n) 和g(n) ，如果对于任意正常数c，存在n0使得对所有n? n0有：f(n) cg(n) ，则称f(n)是g(n)的严格低阶函数或g(n)是f(n)的严格渐近上界，记为f(n)=o(g(n