算法设计和分析

1、烟台大学计算机学院证明正确性分析算法设计程序理解问题精确解或近似解选择数据结构算法设计策略设计算法nIsizeITIp)()()(0limnbnan032! 3! 21iixixxxxexnnenx1limabbalogbaabcccloglog)(loganabnbloglogbaaccblogloglogaabblog)/1 (logbaablog1logacbbcaloglog.5432)1ln(5432xxxxxxxxxx)1ln(10loglim)2(loglimlogabnnabnnnn00)!1(1!nnnnnnn321!nennnn112!neennnn2!nnn1211121

2、)(!nnon )2(!nn)log() !log(nnnif (expression) statement;else statement; exp1?exp2:exp3 y= x9 ? 100:200; 等价于： if (x9) y=100; else y=200;switch (expression) case 1: statement sequence; break; case 2: statement sequence; break; default: statement sequence; return-type function name(para-list) body of th

3、e function int max(int x,int y) return xy?x:y; template Type max(Type x,Type y) return xy?x:y; int i=max(1,2)；double x=max(1.0,2.0)；template void Make2DArray(Type* &x,int rows, int cols) x=new Type*rows; for (int i=0;irows;i+) xi=new Typecols;template void Delete2DArray(Type* &x,int rows) for (int i

4、=0;irows;i+) delete xi; delete x; x=0;templateint seqSearch(Type *a, int n, Type k) for(int i=0;in;i+) if (ai=k) return i; return -1;nIsizeavgITIpnT)()()()(pnnpnnpnpnp1321)1 (2) 1(11pnnppninpnitemplatevoid insertion_sort(Type *a, int n) Type key; / cost times for (int i = 1; i =0 & ajkey ) / c4 sum

5、of ti aj+1=aj; / c5 sum of (ti-1) j-; / c6 sum og (ti-1) aj+1=key; / c7 n-1 ) 1() 1() 1() 1() 1()(7116115114321nctctctcncncncnTniiniinii) 1() 1() 1() 1()(74321minncncncncncnT)()()(743274321nOccccnccccc1112) 1() 1(ninni112) 1(ninni)()(22) 1(2) 1(2) 1(12) 1() 1() 1()(27432765432126547654321maxnOccccncccccccncccncnncnn