软件工程算法设计与分析基础

1、软件工程算法设计与分析基础软件工程学系列2022/8/252主要内容算法的基本概念 算法设计的标准 算法设计的步骤算法的复杂性分析算法设计技巧与策略 NP完全理论 并行算法 综合举例 前一页2022/8/253算法的基本概念前一页 广义：算法是解决一类问题的方法和步骤 精确：算法是求解一类问题的无二义性的有穷过程 2022/8/254算法的基本概念前一页算法有五个重要特征 有穷性：合理的有限性 确定性：确切的含义，无二义性;对相同输入, 有稳定的输出 可行性：算法中的操作可通过已有的基本运算 来实现 输入： 零个或多个输入 输出： 一个或多个输出 2022/8/255算法设计的标准前一页 正确

2、性：正确地解决问题；可用理论证明或验 证来保证 可读性：便于交流、修改、调试 健壮性：抗冲击 高效性：与占用计算机资源成反比，突出的是 计算时间和存储空间 2022/8/256算法设计的步骤前一页问题的陈述：问题的理解与正确陈述 建立数学模型：采用何种数学工具来描述问题 算法的详细设计：实现算法的数据结构与计算 机基本操作序列 算法的正确性：理论证明或验证 算法的实现：编程计算机实现算法分析2022/8/257前一页算法设计的步骤举例例： 从a1，a2，.，an n个元素中找出与x 相 同的第一个元素输入：a1，a2，.，an n个整数,整数x输出：与x相同的第一个元素ai及下标值 I；若 没

3、有与x相同的元素,输出下标值为n+1方法：在a1，a2，.，an中顺序查找,若找到则 结束运算 2022/8/258前一页算法设计的步骤举例procedure find(A,x);begin i1; while (in) and (Aix) do ii+1; print(i) end; 2022/8/259算法的复杂性分析前一页 算法复杂性是算法运行所需要的计算机资源的量，需要的运行时间称为时间复杂性,需要的存储空间称为空间复杂性，突出的是时间复杂性问题。 2022/8/2510算法的复杂性分析前一页问题的大小称为问题的规模,用n表示，如： 2022/8/2511算法的复杂性分析前一页时间复杂

4、性是问题的规模n的函数，记为T(n) 例：在元素a1，a2，.，an (aiai+1)中查找与x 相同的元素。算法1：在a1，a2，.，an中顺次挨个查找，运 算时间主要是比较次数 Tmax(n)=Cn Tmin(n)=C Tave(n)= (1+2+.+n)C/n = (n+1) C /2 2022/8/2512算法的复杂性分析前一页 算法2：对半查找（设n=2k) T(n)=T(n/2)+C T(1)=C 当 n 充分大时，T(n)中主要是高次项起作用，时间复杂性的极限称为渐近时间复杂性。 2022/8/2513算法的复杂性分析前一页若存在C(0)和n0,当nn0时 T(n) CF(n),

5、则称T(n)是 O(f(n)的， f(n)是T(n)增长率的一个上界若T(n)=(f(n),f(n)= (T(n),则称T(n)是 (f(n)的，T(n)与f(n)同次 若存在C0,使T(n)=Cf(n),称T(n)是(f(n)的，f(n)是T(n)的一个下界。通常考虑O(f(n)较多，常用的有: O(1), O(log(n), O(nlog(n), O(n), O(n2), O(n3) O(2n), O(n!)等 2022/8/2514算法的复杂性分析前一页例：对a1，a2，.，an排序（非降次序）算法1：从a1，a2，.，an中找出最小元，与a1 交换,再从a1，a2，.，an中找出最小元

6、，与a2交换.比较次数： T(n)=(n-1)+(n-2)+.+1 =n (n-1)/2=nn/2-n/2是O(n2)的 2022/8/2515算法的复杂性分析前一页算法2：递归地，分片排序后再合并比较次数：T(n)=2 T(n/2)+c n n1 T(1)=c n=1 T(n)=c n+c nlog(n)算法是O(nlog(n)的 2022/8/2516算法的复杂性分析前一页例：前述在a1,a2,.,an(aiai+1)中查找x。 两个算法的时间复杂性分别是O(n)和O(log(n)的 n=260时，n=1.15*1018。 用O(log（n）)算法:查60次即可。 用O(n)算法: 设每秒

7、查1010（10亿次）， 需要1.15*108=3.65年！ 2022/8/2517算法的复杂性分析前一页例:TSP(Traveling Salesman Problem) (货郎担问题)货郎要周游遍n个城市，回到 原地，找一条最短的周游路线。 对于30个城市,穷举法，加运算次数T(n)=n! 30!=2.65*1032，设每秒1012 (1万亿次) 2.65*1020=8.4*1012年，即8.4万亿年 2022/8/2518算法的设计技巧与策略前一页1穷举法2递归技术与分治法 把一个问题分解为K个规模较小的子问题 如:前例中的排序问题 3动态规划 将问题层层分级,逐层求解4贪心算法 找当前

8、最优点(局部最优) 5回溯法 类似于树的深度搜索(状态空间树) 6限界剪枝法 (，剪枝) 类似回溯法,在状态空间上搜索极大目标值 2022/8/2519NP完全理论前一页 通俗地说，一个算法的时间复杂性以多项式为上界则称为多项式算法，多项式为界是一个重要的尺度 2022/8/2520NP完全理论前一页P类、NP类、NPCP=L|L是一个能在多项式时间内被确定型RAM （一种计算模型）接受的语言NP=L|L是一个能在多项式时间内被非确定型 RAM接受的语言 我们把可用多项式算法求解的问题归为一类：P类；把可用非多项式算法求解的问题归为一类：NP类。显然，P NP。 2022/8/2521NP完全

9、性理论前一页 有一类问题，目前为止既找到多项式算法，也不能证明不存在多项式算法，且它们之间有一种联系，只要某个问题有多项式算法，其它问题也有，反之亦然，这类问题称为NPC，共有1000多个问题。目前只能采用近似算法 。2022/8/2522并行算法前一页 并行计算机，曙光1000等 网络并行计算 2022/8/2523综合举例前一页例1：用筛法找出1到10000中的全部素数 算法1： 用a1,a2,a3,.,a10000记录整 数 1，2，3，.,10000; 从2开始，将2的倍数全变为0；. 从2开始，将2的倍数全变为0；.查找次数T1(n)=(n-2)+(n-3)+.+2+1 =n(n-2

10、)/2是O(n2)的 2022/8/2524综合举例前一页#define CONST 10000main() int a 100012; long i,j,k,count,t,kk; char ch; for (i=1;i=10000;i+) ai0=i; ai1=i+1; ; aCONST1=0; k=1; printf(nThe prime number s are:n); 2022/8/2525综合举例 - 例1前一页 while (ak1!=0) k=ak1; printf(%8d,ak0); j=k; while (aj1!=0) if (aaj10%ak0=0) if (aaj11

11、!=0) aj1=aaj11; else aj1=0; ; j=aj1; ; ; ch=getch(); 2022/8/2526综合举例前一页算法2：a100001：存放1，2，.,10000 个整数ai0：第i个数的数值ai1：第i个数的下一个数的下标a202；.；ai0i;a213；.；ai1i+1; 2345678910111213 141516171819. 先找到2是素数，查找到2的倍数就跳过 357 11131719 再找到3是素数，查到3的倍数并跳过 a71a91; a131a151; 35711131719 2022/8/2527综合举例前一页#define CONST 100

12、00main() int a 100012; long i,j,k,t; char ch; for (i=1;i=CONST;i+) ai0=i; ai1=i+1; ;/*赋初值*/ aCONST1=0; /*最后一个元素*/ printf(nThe primes are :n);k=1; 2022/8/2528综合举例前一页while (ak1!=0) k=ak1; printf(%8d,ak0); j=k; while (aj1!=0) if (aaj10%ak0=0) if (aaj11!=0) aj1=aaj11; else aj1=0; ; j=aj1; ; ; ch=getch()

13、; 2022/8/2529综合举例前一页算法3：定义a150012 i:第i个整数；ai0:记录第i个整数的上一个整数；ai1:记录第i个整数的下一个整数；1，2，3，4，5，6，7，8，9，10，11，12，13，14，先消去2的倍数：2，4，8，16，.再消去2*3的倍数：6，12，18，.再消去2*i的倍数：用当前的素数i做基数，消去i*j(i的下一个) 的倍数 2022/8/2530综合举例前一页#define CONST 15000main() int a 150012; long i,j,k,m,count,k1,k2,t; char ch; for (i=1;i=CONST;i+

14、) ai0=i-1; ai1=i+1; ; aCONST1=0; k=2; m=2; 2022/8/2531综合举例前一页while (ak1!=0) printf(%8ld,k); j=m*k; while (j=CONST)&(aj1!=0) for (i=j;i=CONST;i=i*k) aai01=ai1; aai10=ai0; ; m=am1; j=m*k; ; k=ak1; m=k;；ch=getch(); 2022/8/2532综合举例前一页查找1.15000内的素数：算法1：14029031次算法2： 1561055次算法3： 23321次 2022/8/2533综合举例前一页例2：排序问题及算法讨论，设a1,a2,an， 要求按非降次序排序。 考察每种算法需要的比较次数 2022/8/