计算时间复杂度例题
计算时间复杂度
引言
算法是程序的灵魂，想学好算法就必须先搞懂时间复杂度
算时间复杂度就是算基本语句条数
5个计算时间复杂度基础例题
例题一
for(int i=0; i<n; i++){for(int j=i; j<n; j++){System.out.println("执行一次");}}
i=0时，j=0，j循环执行n次
i=1时，j=1，j循环执行n-1次
i=2时，j=2，j循环执行n-2次
推广到
i=n-1时，j=n-1，j循环执行1次
Sn=n+n-1+n-2+…+1=n×(n+1)/2
时间复杂度为：O(n²)
例题二
i=0;while((i+1)*(i+1)<=n){i++;}
第1次，i=1
第2次，i=2
推广到
第x次，i=x
设第x次退出循环，则(i+1)×(i+1)>n
x=i>(√n)-1 次
时间复杂度为：O(√n)
例题三
int i=1;while(i<n){i = i*2;}
第1次：i=21
第2次：i=22
第3次：i=23
……
第x次：i=2x
设第x次退出循环，则有i=2x ≥ n
取对数解得x=logn，共执行logn次
时间复杂度为：O(logn)
例题四
for(int i=1; i<=n; i++){for(int j=1; j<=i; j++){for(int k=1; k<=j; k++){System.out.println("执行一次");}}}
粗略的估计:
最外层i循环n次，j循环最坏的情况执行n次，k循环最坏的情况也执行n次，即时间复杂度为O(n³)
详细计算:
i=1时，j、k循环都只执行一次，输出语句执行1次
i=2时，j循环[1,2]执行2次，每一次分别有一个k循环，分别是[1,1]、[1,2]输出语句执行1+2次
i=3时，j循环[1,3]执行3次，每一次分别有一个k循环，分别是[1,1]、[1,2]、[1,3]输出语句执行1+2+3次
可以推广到
i=n时，j循环[1,n]执行n次，每一次分别有一个k循环，分别是[1,1]、[1,2]……[1,n]输出语句执行1+2+……+n次
总共:Sn=(1)+(1+2)+(1+2+3)+……+(1+2+3+…+n)
1~n项和取n²放大一点看就是n个这样的n²相加，即n³
时间复杂度为：O(n³)
例题五
for(int i=0; i<n; i++){for(int j=2*i; j<n; j++){System.out.println("执行一次");}}
粗略的估计
i=0时，j=0，内循环n次
即时间复杂度为O(n²)
详细计算
i=0时，j=0，[0,n)内循环n次
i=1时，j=2，[2,n)内循环n-2次
i=2时，j=4，[4,n)内循环n-4次
推广到
i=(n/2)-1，j=n-2，[n-2,n)内循环2次
i=n/2时，j=n，跳出循环
综上Sn=n+n-2+n-4+…+2
共n/2项，首项为n，公差-2
Sn=(((n/2)×[(n/2)-1)]×(-2)/2) + (n/2)×n
输出语句执行了(n²+2n)/4次
时间复杂度为：O(n²)
总结
一定要学会算时间复杂度
很重要
很重要
很重要