今天在看算法时, 遇见了一些问题, 想了很久, 现总结如下, 关于 for 循环的时间复杂度. 我们知道当一重 for 循环时
- package Suanfa;
- public class Fortest { public static void main(String[] args) {
- int n=100,count=0;
- for(int i=0;i<n;i++) {
- if(true) {
- count++;
- }
- }
- }
- }
这是最简单的 for 循环, count 执行 n 次, 时间复杂度是 N;
如果是 for 的二重循环呢
- package Suanfa;
- public class Fortest {
- public static void main(String[] args) {
- int k=100 ,count=0;
- for(int i=0;i<k;i++)
- for(int j=i+1;j<k;j++)
- {
- if(true)
- count++;
- }
- System.out.println("k 值为:"+k);
- System.out.println("count 值为 :"+count);
- }
- }
可以看见 count 输出 4950; 一般刚接触时, 就会觉得这事件复杂度是 n 的平方, 当然一般这样说也没错, 但是你有没想过, 为什么 k 输入是 100 时, count 输出是 4950, 如果 k 是其他值呢,
count 又会是什么, 两者之间有什么关系? 如果 for 是三重循环又会是怎样呢?
三重循环的情况如下:
- package Suanfa;
- public class Test {
- public static void main(String[] args) {
- int k=100 ,count=0;
- for(int i=0;i<k;i++)
- for(int j=i+1;j<k;j++)
- for(int x=j+1;x<k;x++)
- {
- if(true)
- count++;
- }
- System.out.println("k 值为:"+k);
- System.out.println("count 值为 :"+count);
- }
- }
可以看见 count 输出为 161700, 当然你也可以试着把 k 改小一点, 当然你要试着探究 k 和 count 的关系, 在二重 for 循环, 三重 for 循环, 甚至
更多 for 的情况下, 现在我们先讨论二重 for 循环下 的情况: 假定 k 值为 n; 那么要使 if 语句能够执行; 需满足
i 0 1 2 3 ...... n-2 n-1
j 1 2 3 4 ...... n-1.
当 i 为 0 时, j 可取 1 到 n-1, 使得 if 语句能够有效执行; 同理 i=1 时, j 可取 2 到 n-1;
i=0; j = 1,2,3,4.....n-1;(if 语句执行 (n-1)-1+1 次 即 n-1 次)
i =1 ,j =2,3,4....n-1; (if 语句执行 (n-1)-2+1 次 即 n-2 次)
- i=2 , j =3,4,5...n-1;
- ...
- i=n-2,j =n-1 (if 语句执行一次)
可得 if 语句执行的总次数为: (n-1+1)(n-1-1+1)/2 = (n-1)*n/2, 你也可以理解为 C(2 n)(姑且这样表示吧), 这个东东不知道怎么表示, 就是和二项式系数有关的那个, 2 是上角标, n 是下角标;
C(2 n)=n*(n-1)/(2*1);
三重循环时: 假定 k 值为 n; 那么要使 if 语句能够执行; 需满足:
i 0 1 2 3 ...... n-3
j 1 2 3 4 ...... n-2.
x 2 3 4 5 ........ n-1
经过如上推算, 可得 if 语句执行总次数为 C(3 n) = n*(n-1)*(n-2)/(3*2*1)=n*(n-1)*(n-2)/6;
四重 for 循环 , 可得 if 语句执行总次数为 C(3 n) = n*(n-1)*(n-2)*(n-4)/(4*3*2*1)=n*(n-1)*(n-2)/24;
如果你觉得哪里不对, 可以指出, 欢迎评论, 本文将不定期更新.