算法分析方法

1、算法设置校正和分析、算法分析方法、1 .算法复杂性分析、算法复杂性=算法所需的校正器资源算法的时间复杂性T (n )算法的空间复杂性S (n )。 算法的处理器复杂性P (n )其中n是问题的规模(输入大小)，算法是大小n的所有实例所需时间的最大值，1 .算法的时间复杂性，最坏情况下的时间复杂性tmax (n )=max t (I )|size (T (n) t (n) )/T (n) 0、as n。 t (n )为t (n )的渐近状态，称为算法的渐近复杂性。 在数学上，t (n )是t (n )的渐近表达式，t (n )是省略下位项留下的主项。 比T (n )更简单的例子如果存在T(n)=

2、3n2 4nlog2n 7 t(n)=3n2、(t (n )-t (n ) )/t (n )=(4nlog2n7)/(3n 2实常数c 0和调整常数n0 1，对于每个n n0的整数，如果满足0 f (n) cg (n )，则f(n )为整数。 也可以读作“f(n )是g(n )的大的o”或“f(n )是g(n )级的”。 渐近上界符号o，例1-1 7n-2是O(n )。 证明：从大的o的定义可知，有必要寻找实常数c 0和整常数n0 1，对于每n n0的整数满足7n-2 cn。 可能的选择中的一个是c=7和n0=1，实际上这只是无数个选择中的一个。 这是因为大于7的实数c和1以上的整数n0都满足

3、条件。 渐近上界符号o，例子1-2 20n3 10nlogn 5是O(n3)。 证明：对于n 1，20 n 310 nlogn 535 n 3。 事实上，aknk ak-1nk-1 a0总是O(nk )。 渐近上界符号o，例子1-3 3logn loglogn是O(logn )。 证明：对于n2、3lognloglogn4logn。 因为n=1，loglogn没有意义。 渐近上界符号o，例子1-4 2100是O(1)。 证明：对于n 1，21002100 * 1。 因为变量n不会出现在不等式中，所以我们处理一定值函数。 大的o符号的使用，因为大的o符号已经表示“以下”的概念，所以没有写成“f(

4、n) O(g(n )”。 同样地，“f(n)=O(g(n ) )”这样的说法虽然很常见，但是最好是说完全不正确(在通常理解的“=”关系中)，“f(n) O(g(n )”这样的“f(n )是O(g(n ) )”。 如果偏重于数学语言，称为f(n) O(g(n ) )也是正确的。 因为大o表示技术上定义函数的全集。 渐近分析的符号，(1)O(f) O(g)=O(max(f，g)(2)o(f)o(g)=o(fg )。 规则O(f(n) O(g(n)=O(max(f(n )，g(n ) )的证明：与任意的f1(n) O(f(n ()同样，对于任意的g1(n) O(g(n ) )存在正常数c2和自然数n

5、2，对于所有的n n2都存在g(n ) 假设c3=最大c 1、c2、n3=最大n 1、n2、h (n )=最大(n )、g(n )。 对于所有的n n3，存在具有f1(n ) g1(n ) c1f(n ) c2g (n ) c3f (n )=c3(f ) g (n )的实常数c 0和调整常数n0 1，如果对于n n0满足f (n) cg (n )，则f (n ) 同样，如果f(n )是O(g(n ) )，而f(n )是(g(n ) )，则f(n )是(g(n ) )。 实际常数c0和c”0和整数n0 1，对于n n0满足cg(n) f(n)c”g(n )，3 .渐近下界符号的实例153证明：3

6、logn loglogn 3logn，n 2。 本例示出了当产生大的下界时低阶项可以被忽略。4 .渐近边界符号，示例1-6 3logn loglogn是(logn )。 证明：可以从例1-3和例1-5得到。大o的渐近符号小o，f(n )和g(n )是将整数映射到实数的函数。 如果相对于任意常数c 0存在常数n0，相对于n n0满足f (n) cg (n )，则f(n )为o(g(n)(f(n )为g(n )”)如果相对于读出的任意常数c 0存在常数n0，相对于n n n 0满足cg (n) f(n )，则f(n )为n (n )。 非正上边界符号o和非正下边界符号，例子1-7 f(n)=12n

7、2 6n是o(n3)和(n )首先证明f(n )是o(n3)。 下面证明f(n )是(n )。 假设c(0)再次为常数，n0=12/c .那么对于n n0，可以获得12n-26n-12n-2cn，从而f(n )是(n )，并且在渐近分析符号的等式和不等式中的意义是f (。 通常，方程式和不等式中的渐近符号(g(n ) )表示(g(n ) )中的一个函数。 例如，2n2 3n 1=2n2 (n )表示2n2 3n 1=2n2 f(n )，其中f(n )是(n )中的一个函数。 等式和不等式中渐近符号o、o、和的意义相似。 渐近分析中的函数比较，f(n)=O(g(n) a b； f(n)=(g(n

8、) a b。 f(n)=(g(n) a=b。 f(n)=o(g(n) a b .5 .渐近分析符号的一些性质，(1)传输性： f(n)=(g(n ) )，g(n) f(n)=O(g(n ) )，g(n)=O (h(n) f(n)=O (h(n )。 f(n)=(g(n ) )，g(n)=(h(n) f(n)=(h(n ) )。 f(n)=o(g(n )，g (n )=o (n )，f(n)=o(g(n )。 f(n)=(g(n ) )，g(n)=(h(n) f(n)=(h(n ) )。 渐近分析符号的一些性质，(2)反体性： f(n)=(f(n ) )； f(n)=O(f(n): f(n)=(

9、f(n ) ) .渐近分析符号的一些性质，(3)对称性： f (n )=o (g ) ) g (n )=(f (n ) f (n )=o (g ) ) g (n )=(f (n ) )。 渐近分析符号的一些性质，算术运算： O(f(n) O(g(n)=O(maxf(n )，g(n ) )； O(f(n) O(g(n)=O(f(n) g(n ) )。 O(f(n)*O(g(n)=O(f(n)*g(n ) )。 o (cf (n ) )=o (f (n ) ):g (n )=o (f (n ) ) o (g (n ) )=o (f (n )。 6、算法渐近复杂性分析中常用的函数，(1)单调函数单调

10、递增： m n f(m) f(n )； 单调递减： m n f(m) f(n )； 严格单调增加： m f(n). (2)整数函数x:x以下的最大整数； x:x以上的最小整数。 多项式函数p(n)=a0 a1n a2n2 adnd。 ad0； p(n)=(nd )； f(n)=O(nk) f(n )多项式具有边界。 f(n)=O(1) f(n) c 指示符号的数量是多少？ k d p(n)=o(nk): k d p(n)=(nk )，校正算法渐近复杂性分析中使用的函数，(4)指数函数对于正整数m，n和实数a0: a0=1。 a1=a； a-1=1/a； (am)n=amn； (am)n=(an)m； 阿曼=阿姆n； a1 an是单调递增函数a1 nb=o(an )，ex 1 x； |x| 1 1 x ex 1 x x2； ex=1 x (x2)、as x0。 对数函数log n=