关于时间复杂度,自学数据结构以来除了一些简单的循环,其他的根本就找不到思路,请问大家对此问题的方法

那请问一下,频度是怎样的,能举个例子吗?谢谢了

关于时间复杂度个人学习的策略:
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编辑过]

谢谢啦．有点思路了！