关于时间复杂度,自学数据结构以来除了一些简单的循环,其他的根本就找不到思路,请问大家对此问题的方法
关于时间复杂度个人学习的策略:
1.理解书本基本的概念(尤其是语句的频度)
2.会分析循环语句的执行所满足的条件,从而确定循环次数(一般是问题规模n的函数)
3.了解常用的数量级(如:O(1),O(n),O(n^2),O(n^3)…………O(lgn)等增长关系比较)
当然了,仅知道上面还不能见题能解!需要你有一定的数学素质(数列,指对方程,不等式会经常成为出题的目标)。如果你数学狂差的话,要好好补补了!(哈哈!!本人是数学系出生的(优势了))
下面举两例加以说明,望朋友们慢慢体会喽
例1.分析下列算法段的时间频度及时间复杂度 ______________数列方法的运用
for (i=1;i<=n;i++)
for (j=1;j<=i;j++)
for ( k=1;k<=j;k++)
x=i+j-k;
分析:i=1时,j=1;k=1 ; (循环1次)
i=2时,j=1;k=1 循环1次; j=2,k=1 循环1次 ; j=2;k=2 循环1次 (共循环1+2次)
i=3时,j=1,k=1 循环1次; j=2,k=1 循环1次 ; j=2,k=2 循环1次
j=3;k=1 , 2 ,3 循环3次 (共循环1+2+3次)
…………
…………
i=n时,……(归纳可得:共循环1+2+3+……+n = n(n+1) / 2 次)
所以,语句“ x=i+j-k”在整个循环中一共执行次数为(1)+(1+2)+(1+2+3)+(1+2+3+4)+……(n(n+1) / 2 )=n/6(n+1)(2n+1)=O(n^3)
(其中用到对等差数列的前n项和的和数列再求和的拆项技巧;体现了对数学的要求)
例2.下程序中带划线的语句的执行次数的数量级( O( log2(n) ) ) _____指数不等式的运用
i=1;
WHILE i<n DO
i=i*2
分析:此题循环条件是:i<n ,而i的值每循环一次就是原来的2倍;
但循环的次数不像上例那样好归纳;故可设循环次数(频度)为T(n)
由i的值每循环一次就是原来的2倍可得不等式
2^T(n)<n
得T(n)<log2(n)
取最大值有数量级O( log2(n) )
通过以上的分析,可见数据结构的学习需要一个好的数学功底!!
以上仅代表个人意见,勿以语言攻击!!
谢谢阅读!!望交流
只希望学到更多的东西!
[此贴子已经被作者于2006-3-21 12:33:39编辑过]