时间空间复杂度

概念：

　　时间复杂度：当前算法执行的时间；由于一个算法执行时花费的时间与执行次数成正比，所以可以通过执行

　　　　　　　　次数来表示；

　　空间复杂度：当前算法需要占用的内存空间；

使用：

• 时间复杂度

　　表示法：大O表示法，即T(n)=O(f(n))；

　　例如：

for(i=0;i<n;i++){
   j=i;
   j++;  
}

　　分析：时间复杂度公式T(n)=O(f(n))，其中 f(n) 表示每行代码执行的次数之和，而O表示正比例关系；

　　　　　故上面的时间复杂度为O(n);

　　常见的时间复杂度量级：

1. 1. 常数阶 O(1)
      

      int i=1，j=2;
      ++i;
      j++;
      int sum=i+j;

      分析：上述代码的执行不跟随某个变量而变，所以无论多长的代码都只执行一次，时间复杂
      度可以用O(1)表示；                                 

   2. 对数阶 O(logN)
      

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

      分析：从上面代码可以得到当每次*2的时候等价于2的x次方等于n；故可以得到这样的一个
      公式：2^x=n，故x=log2^n；因此时间复杂度为O(logN)

   3. 线性阶 O(n)
      

      for(i=0;i<=n;i++){
           j=i;
           j++;  
      }

      分析：for 循环中的代码执行次数为n次，因为时间随着n的变化而变化，故这类代码可以用
      O(n)来表示时间复杂度；

   4. 线性对数阶 O(nlogN)　
      

      for(m=1;m<n;m++){
         i=1;
         while(i<n){
             i=i*2;
         }  
      }

      分析：有了上面对数阶的理解，针对线性对数阶来讲只是在外面加了一个循环体而已，所
      有就是n*O(logN)即O(nlogN)；

   5. 平方阶 O(n^2)
      

      for(x=1;x<=n;x++){
         for(y=1;y<=n;y++){
             j=i;
             j++;
         }  
      }

      分析：平方阶很容易理解就是2层n循环；

   6. 立方阶 O(n^3)
      分析：类似平方阶只不过嵌套3层n循环；
   7. k次方阶 O(n^k)
      分析：类似平方阶只不过嵌套k层n循环；
   8. 指数阶O(2^n)　　　　　
      分析：随后有实例会补充该复杂度的情况；

• 空间复杂度
  有了时间复杂度的概念之后，空间复杂度也很简单；也就是算法占用的空间大小
  

  int i=1，j=2;
  ++i;
  j++;
  int sum=i+j;

  分析：上面代码不随处理数据而变化，故空间复杂度为O(1)；

  int[] m=new int[n];
  for(i=1;i<=n;i++){
     j=i;
     j++;
  }

  分析：上面代码只是在循环体外声明了变量占用了一定的内存，而循环体内却没有，因此空间
  复杂度为O(n)；

  　　

时间空间复杂度

原文：https://www.cnblogs.com/gamecc666/p/14630202.html