算法的时间复杂度和空间复杂度

时间复杂度

要理解时间复杂度，需要先理解时间频度。

一个算法中 语句执行的次数 称作语句频度（时间频度）。记作T(n)。

那么时间复杂度如下定义：

若某个辅助函数f(n)，使得当n趋近于无穷大时，T(n)/f(n) 的极限值为不等于零的常数，那么称f(n)是T(n)的同数量级函数。记作T(n)=O(f(n))，并且，称O(f(n))为算法的渐进时间复杂度，简称时间复杂度。

举例
example1

int x = 1;   //时间复杂度O(1)
for(int i = 0; i<n; i++){
  system.out.println(i);
}   //时间复杂度O(n)

example2

int n=100, count=0;
for(int i=0; i<=n; i*=2){  
  for(int j=1; j<=n; j++){
    count++;
  }
}  //复杂度O(nlog2n) -> 最外层log2n与内层n相乘

拓展：N与NP问题

Ο(2^n)＜Ο(n!)为指数时间复杂度，称为NP（Non-Deterministic Polynomial, 非确定多项式）类问题。

Ο(log2n)，Ο(n)，Ο(nlog2n)，Ο(n^2)为P类问题，该算法为有效算法。

空间复杂度

运行完一个程序所需内存的大小。也可以简单理解为临时变量占用的存储空间。

举例
example

//该程序的空间复杂度为O(1)
int x=1, y=2;
int temp=x;
x=y;
y=temp;