概念
时间复杂度
是度量算法执行的时间长短，时间复杂度是指他运行时计算的次数。
一般情况下，算法的基本操作重复执行的次数是模块n的某一个函数f(n)，因此，算法的时间复杂度记做：T(n)=O(f(n))
随着模块n的增大，算法执行的时间的增长率和f(n)的增长率成正比，所以f(n)越小，算法的时间复杂度越低，算法的效率越高。
在计算时间复杂度的时候，先找出算法的基本操作，然后根据相应的各语句确定它的执行次数，再找出T(n)的同数量级（它的同数量级有以下：1，$log_{2}n$，n，$nlog_{2}n$，n的平方，n的三次方，2的n次方），找出后，f(n) = 该数量级，若T(n)/f(n)求极限可得到一常数c，则时间复杂度T(n) = O(f(n)。
按数量级递增排列，常见的时间复杂度有：常数阶O(1)，对数阶O(log2n)，线性阶O(n)，线性对数阶O(nlog2n)，平方阶O($n^2$)，立方阶O($n^3$),…，k次方阶O($n^k$)，指数阶O($2^n$)。随着问题规模n的不断增大，上述时间复杂度不断增大，算法的执行效率越低。
空间复杂度
是度量算法所需存储空间的大小，空间复杂度是指运行完一个程序所需内存的大小。在算法中所谓的空间复杂度为O(1)并不是说只使用一个空间，而是说在待处理的数据量变化的情况下使用的空间量是不变的。空间复杂度一般算的是辅助空间的大小，如果这个辅助空间的大小不随元素N变化那么就是O(1)。
例如：冒泡排序，需要的辅助空间是一个作交换用的临时变量，而且无论任何情况下都只要这一个，所以空间复杂度就是O(1)。但桶排序就不同了，本身需要M个桶，桶的数量是人为决定的，然后需要N个结点，去装原本的N个元素，所以空间复杂度就是O(M+N)。
一个程序的空间复杂度是指运行完一个程序所需内存的大小。利用程序的空间复杂度，可以对程序的运行所需要的内存多少有个预先估计。一个程序执行时除了需要存储空间和存储本身所使用的指令、常数、变量和输入数据外，还需要一些对数据进行操作的工作单元和存储一些为现实计算所需信息的辅助空间。
程序执行时所需存储空间包括以下两部分。
固定部分。这部分空间的大小与输入/输出的数据的个数多少、数值无关。主要包括指令空间（即代码空间）、数据空间（常量、简单变量）等所占的空间。这部分属于静态空间。
可变空间，这部分空间的主要包括动态分配的空间，以及递归栈所需的空间等。这部分的空间大小与算法有关。
一个算法所需的存储空间用f(n)表示：S(n)=O(f(n))，其中n为问题的规模，S(n)表示空间复杂度。
示例
时间复杂度
$n^3$
1
2
3
4
5
6
7
8
9
| for(i=1; i<=n; ++i)
{
for(j=1; j<=n; ++j)
{
c[i][j] = 0;
for(k=1; k<=n; ++k)
c[i][j] += a[i][k] * b[k][j];
}
}
|
则有T(n) = n的平方+n的三次方，根据上面括号里的同数量级，我们可以确定n的三次方为T(n)的同数量级，则有f(n) = n的三次方，然后根据T(n)/f(n)求极限可得到常数c，则该算法的时间复杂度：T(n) = O($n^3$) 。注：$n^3$即是n的3次方。
O(n)：
1
2
3
4
| int x = 1;
for(int i=0; i<n; i++) {
System.out.println(i);
}
|
O(1)：
O($log_{2}n$)：
1
2
3
4
| int n = 8, count = 0;;
for(int i=1; i<=n; i *= 2) {
count++;
}
|
O($n^2$)
1
2
3
4
5
6
| int n = 8, count = 0;;
for(int i=1; i<=n; i++) {
for(int j=1; j<=n; j++) {
count++;
}
}
|
O($nlog_{2}n$)
1
2
3
4
5
6
| int n = 8, count = 0;;
for(int i=1; i<=n; i *= 2) {
for(int j=1; j<=n; j++) {
count++;
}
}
|
时间复杂度
O(1)
一个临时变量temp，所以空间复杂度为O(1)
1
2
3
4
| int x=1, y=2;
int temp = x;
x = y;
y = temp;
|
