1、算法分析与设计算法分析与设计 Algorithm Design i2;
2) while in do 3) if MAX0 ， 存在正数 和n0 0使得对所有nn0有：0cg(n)f(n) 等价于f(n)/g(n) ， as n 。
f(n)(g(n) g(n)o(f(n) 1.6 算法复杂性分析算法复杂性分析 渐近分析记号的若干性质 （1）传递性： f(n)=(g(n) ， g(n)=(h(n) f(n)=(h(n)； f(n)=(g(n) ， g(n)=(h(n) f(n)=(h(n)； f(n)=(g(n) ， g(n)=(h(n) f(n)=(h(n)； f(n)=(g(n) ， g(n)=(h(n) f(n) 。

2、=(h(n)； f(n)=(g(n) ， g(n)=(h(n) f(n)=(h(n)； （2）反身性： f(n)=(f(n)；f(n)=(f(n)；f(n)=(f(n). （3）对称性： f(n)=(g(n) g(n)=(f(n) . （4）互对称性： f(n)=(g(n) g(n)=(f(n) ；f(n)=(g(n) g(n)=(f(n) ； （5）算术运算： (f(n)+(g(n) = (maxf(n),g(n) ； (f(n)+(g(n) = (f(n)+g(n) ；(f(n)*(g(n) = (f(n)*g(n) ； (cf(n) = (f(n) ；g(n) = (f(n) (f(n)+( 。

3、g(n) = (f(n)。
1.6 算法复杂性分析算法复杂性分析 规则(f(n)+(g(n) = (maxf(n),g(n) 的证明： 对于任意f1(n) (f(n)， 存在正常数c1和自然数n1 ， 使得 对所有n n1 ， 有f1(n) c1f(n)。
类似地 ， 对于任意g1(n) (g(n) ， 存在正常数c2和自然数 n2 ， 使得对所有n n2 ， 有g1(n) c2g(n)。
令c3=maxc1, c2 ， n3 =maxn1, n2 ， h(n)= maxf(n),g(n)。
则对所有的n n3 ， 有 f1(n) +g1(n) c1f(n) + c2g(n) c3f(n) + c3g(n)= c3(f( 。

4、n) + g(n) c32 maxf(n),g(n) 2c3h(n) (maxf(n),g(n). 1.6 算法复杂性分析算法复杂性分析 取整函数 x ：不大于x的最大整数； x ：不小于x的最小整数 。
取整函数的若干性质 x-1 x x x 0 ， 有： n/a /b = n/ab ;
n/a /b = n/ab ;
a/b (a+(b-1)/b;
a/b (a-(b-1)/b;
其中 ， f(x)= x , g(x)= x 为单调递增函数 。
1.6 算法复杂性分析算法复杂性分析 算法分析中常见的复杂性函数 1.6 算法复杂性分析算法复杂性分析 小规模数据复杂性增长图 1.6 算法复杂性分析算法复杂 。

5、性分析 中等规模数据复杂性增长图 小结小结 程序与算法 渐进表达式 程序复杂性 （1）选择语句：）选择语句： （1.1) if 语句：语句： （1.2) ？语句：？语句： if (expression) statement;
else statement;
exp1?exp2:exp3 y= x9 ? 100:200;
等价于： if (x9) y=100;
else y=200;
（1.3) switch语句：语句： switch (expression) case 1: statement sequence;
break;
case 2: statement sequence;
break 。

6、;
default: statement sequence;
（2）迭代语句：）迭代语句： （2.1) for 循环：循环： for (init;
condition;
inc) statement;
（2.2) while 循环：循环： while (condition) statement;
（2.3) do-while 循环：循环： do statement;
while (condition);
（3）跳转语句：）跳转语句： （3.1) return语句：语句： return expression;
（3.2) goto语句：语句： goto label;
label: （4）函数：）函数 。

7、： 例：例： return-type function name(para-list) body of the function int max(int x,int y) return xy?x:y;
（5）模板）模板template ： template Type max(Type x,Type y) return xy?x:y;
int i=max(1,2)； double x=max(1.0,2.0)； （6）动态存储分配： （6.1）运算符）运算符new ： 运算符new用于动态存储分配 。
new返回一个指向所分配空间的指针 。
例：int x；y=new int；y=10； 也可将上述 。

8、各语句作适当合并如下： int y=new int；y=10； 或 int y=new int(10)； 或 int y；y=new int(10)； （6.2）一维数组）一维数组 ： 为了在运行时创建一个大小可动态变化的一维浮点数组x ， 可先将x声 明为一个float类型的指针 。
然后用new为数组动态地分配存储空间 。
例：例： float x=new floatn； 创建一个大小为n的一维浮点数组 。
运算符new分配n个浮点数所需的 空间 ， 并返回指向第一个浮点数的指针 。
然后可用x0 ， x1 ， xn-1来访问每个数组元素 。
（6.3）运算符）运算符delete ： 当动态分配的存储空间已不再需要时应 。

【第一章|第一章：算法概述】9、及时释放所占用的空间。
用运算符delete来释放由new分配的空间 。
例：例： delete y； delete x； 分别释放分配给y的空间和分配给一维数组x的空间 。
（6.4）动态二维数组）动态二维数组 ： 创建类型为Type的动态工作数组 ， 这个数组有rows行和cols 列 。
template void Make2DArray(Type* for (int i=0;
irows;
i+) xi=new Typecols;
当不再需要一个动态分配的二维数组时 ， 可按以下步骤释放它所占用的空间。
首先释放在for循环中为每一行所分配的空间 。
然后释放为行指针分配的空 间 。
释放空间后将x置为0 ， 以防继续访问已被释放的空间 。
template void Delete2DArray(Type* irows;
i+) delete xi;
delete x;

稿源：(未知)

【傻大方】网址：/a/2021/0820/0023836768.html

标题：第一章|第一章：算法概述