时间复杂度

• 假如 A算法执行时间是一个常数 不随着数据量变大而变大 这样我们认为A算法的时间复杂度就是 O(1)

  • 在数组中通过 数组下标获得某个元素
    • 读取 arr[1] 和arr[1000] 对应的算法的时间复杂度就是O(1)

• 假如 算法的执行时间和数据n是有线性关系的 我们认为这个算法的时间复杂度是O(n)

  • 查找一个元素是否在这个数组中
    • (1+n)/2 = 1/2+n/2 ≈ n/2 ≈ n

• 时间复杂度	n=8	n=10	n=100	n=1000
  O(1)	1	1	1	1
  O(logn)	3	3.32	6.64	9.96
  O(n)	8	10	100	1000
  O(nlogn)	24	33.2	66.4	99.6
  O(n^2)	64	100	10000	1000000

算法时间复杂度

• 循环
• 递归上

如何计算

• 三条原则

• 一个循环的时间代价=循环次数*循环的简单语句数目

  •  for(int i=1;i<n;i++){
    //O(n)	
    }

• 多个并列循环 =各个循环次数之和

  • for(int i=1;i<n;i++){
    	//O(n)	
    }
    for(int i=1;i<m;i++){
    	//O(m)	
    }
    O(n)+O(M)

• 嵌套的循环 = 各层之积

•  for(int i=1;i<n;i++){
   	//O(n)	
       for(int i=1;i<m;i++){
   		//O(m)	
   	}
   }
   
   O(n)*O(M)

• O(1)

  • int a= 3;

• O(n)

  • for i=1;i<n;i++

• O(logn)

  • for i=1;i<n;i*=2

• O(n^2)

  • for i=1;i<n;i++
    • for j=1;j<n;j++

• O(nlogn)

  • for i=1;i<n;i*=2
    • for j=1;j<n;j++

• O(n)

  • for i=1;i<n;i*=2
    • for j=1;j<i;j++
  • 1+2+4+8+...+2^logn=2n-1