数据结构 时间复杂度
频度是语句执行的次数.
就本题来分析:
i=1时,@执行1次.
i=2时,@执行1+2次
i=3时,@执行1+2+3次.
i=4时,@执行1+2+3+4次.
...
i=n时,@执行1+2+3+...+n次
所以当i从1到n时总共执行了1+(1+2)+(1+2+3)+...+(1+2+3+...+n)次
即n(n + 1)(n +2)/6
即n³/6 + n²/2 + n/3
频度就是n³/6 + n²/2 + n/3
时间复杂度是:O(n³)
数据结构中算法的时间复杂度是什么？
程序所用时间关于数据规模的函数
比如：
给n个数排序需要n^2的时间
时间复杂度就是O（n^2）
通常有
O(2) 常数 与输入数据规模无关
O(n) 成正比
O(log2n) 平方与数据规模成正比
O(n^2) 与数据规模的平方成正比
O(n^3) ……三次方……
O(n!) 阶乘
数据结构中算法的时间复杂度怎么理解？
就是基本操作语句执行的次数
如果你能确定基本执行语句，那就可以假设需要执行的次数是N，然后根据程序的控制部分得到关于N的一个函数，就可以求的了。
如
int int=3；
do{
i*=3；
）while（i<100）；
那么我们可以这样立即，就是i*=3是基本语句，do~while是控制结构，在控制结构下，要保证
i*=3执行N此后，能使得最后i<100退出控制结构。
那么你去算吧，对于i来说，每次都是乘以3，那执行N次，就相当于乘了n个3，然后满足了<100、因此可以组成一个函数 就是3的n次方<100那你解方程来求N
就得了。
不过时间复杂度用渐进函数表示的。
数据结构算法的时间复杂度
按照分析惯例，假设所有单一运算的时间复杂度均为1
x=n; ......1
while(x>=(y+1)*(y+1)) ......4(两次加法、1次乘法、1次比较)
y=y+1 ......1
时间复杂度 = 1 + (4 + 1) x 循环次数
循环次数是由n和y的初始值决定的，假设循环次数为N，y的初始值为y0，y的结束状态为yn，有
x < (yn + 1)*(yn + 1) ......假设y的初始值为整数，则yn为满足该式的最小整数
N = (yn - y0) / 1 ......因为每次循环y的递增量为1
1式简化为 x = (yn + 1)*(yn + 1)，可得：yn = n^(1/2) - 1
所以N = n^(1/2) - 1 - y0
采用大O表示法，仅考虑最高次项，则求N的复杂度为O(n^(1/2))
进而求得你这3行代码的
总体复杂度 = 1 + (4 + 1) x O(n^(1/2))
由于已知的常数项及非最高次项通常会被忽略（大O精神），所以总时间复杂度为O(n^(1/2))