数据结构之计算时间复杂度_for (i=1;i

时间复杂度指的是算法执行时间所花费的CPU时间量。

（1）简单语句：int count = 0; 

         时间复杂度：O(1）

（2）执行n次的循环语句：for( int i = 1;i < n;i++){ ........}

         时间复杂度：O(n)

（3）执行对数级log₂n次的循环语句：for(int i = 1;i < n;i = i*2 ){........}

         时间复杂度：O(log₂n)

（4）执行平方级n²次的循环语句：情况一：for(int i = 1;i < n;i++){  for(int j = 1;j < n;j++) { ..........}}

         情况二：for(int i = 1;i < n;i++）{  for(int j = 1;j <ｉ；ｊ＋＋){................}}　(1+2+3+....+n) = n(n+1)/2

         时间复杂度：O(n²)

（5）执行nlog₂n次的循环语句：for(int i = 1;i < n;i++）{  for(int j = 1;j < n;j = j * 2){ ........}}

         时间复杂度：O(nlog₂n)

疑惑：

for(int i = 1;i <= n;i = i* 2){

   for(int j = 1;j <= i;j++){

     .........

   }

}

外层循环执行1+log₂n次，i取值1,2,4,8,....内层循环i次，j随外层循环的增加而增加，总循环次数时间复杂度为O(n)