1 时间复杂度

时间频度

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

时间复杂度

描述时间频度随问题规模n的变化规律。

一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数，用T(n)表示，若有某个辅助函数f(n),使得当n趋近于无穷大时，T（n)/f(n)的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数。记作T(n)=Ｏ(f(n)),称Ｏ(f(n)) 为算法的渐进时间复杂度，简称时间复杂度。

最坏时间复杂度和平均时间复杂度

一般不特别说明，讨论的时间复杂度均是最坏情况下的时间复杂度。

2 空间复杂度

一个程序的空间复杂度是指运行完一个程序所需内存的大小。利用程序的空间复杂度，可以对程序的运行所需要的内存多少有个预先估计。一个程序执行时除了需要存储空间和存储本身所使用的指令、常数、变量和输入数据外，还需要一些对数据进行操作的工作单元和存储一些为现实计算所需信息的辅助空间。

程序执行时所需存储空间包括以下两部分。　　
（1）固定部分。这部分空间的大小与输入/输出的数据的个数多少、数值无关。主要包括指令空间（即代码空间）、数据空间（常量、简单变量）等所占的空间。这部分属于静态空间。
（2）可变空间，这部分空间的主要包括动态分配的空间，以及递归栈所需的空间等。这部分的空间大小与算法有关。
一个算法所需的存储空间用f(n)表示。S(n)=O(f(n))　　其中n为问题的规模，S(n)表示空间复杂度。

举例

时间复杂度

时间复杂度简单的理解就是执行语句的条数。如果有循环和递归，则忽略简单语句，直接算循环和递归的语句执行次数。
比如：

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

具体例子：
1、O(1)

int x = 1;  

2、O(n)

for(int i=0; i<n; i++) {  
    System.out.println(i);  
}  

3、O(

)

int n = 8, count = 0;;  
for(int i=1; i<=n; i *= 2) {  
    count++;  
}  

4、

int n = 8, count = 0;;  
for(int i=1; i<=n; i++) {  
    for(int j=1; j<=n; j++) {  
        count++;  
    }  
}  

5、

int n = 8, count = 0;;  
for(int i=1; i<=n; i *= 2) {  
    for(int j=1; j<=n; j++) {  
        count++;  
    }  
}  

空间复杂度
空间复杂度也很简单的理解为临时变量占用的存储空间。一个简单例子：

//交换两个变量x和y  
int x=1, y=2;  
int temp = x;  
x = y;  
y = temp;  

一个临时变量temp，所以空间复杂度为O(1)。