名词解释
算法（Algorithm）是指解题方案的准确而完整的描述，是一系列解决问题的清晰指令，算法代表着用系统的方法描述解决问题的策略机制。不同的算法可能用不同的时间、空间或效率来完成同样的任务。一个算法的优劣可以用空间复杂度与时间复杂度来衡量。
时间复杂性，又称时间复杂度，算法的时间复杂度是一个函数，它定性描述该算法的运行时间。这是一个代表算法输入值的字符串的长度的函数。时间复杂度常用大O符号表述，记做T(n) = O(f(n))，不包括这个函数的低阶项和首项系数。使用这种方式时，时间复杂度可被称为是渐近的，亦即考察输入值大小趋近无穷时的情况。
空间复杂度(Space Complexity)是对一个算法在运行过程中临时占用存储空间大小的量度，记做S(n)=O(f(n))。
时间复杂度计算示例
以下函数共执行 (n+1)+n+1 = 2n+2 次，根据上述名词解释，可记做 T(n) = 2n+2，即 f(n) = 2n + 2，省略低阶项与首项系数可得 f(n) = n，所以该函数的时候复杂度为 O(n)。由于时间复杂度描述的不是函数执行的具体时间，而是表示算法的变化趋势，所以我们主要关注函数中对函数运行时间影响最大的项，因此可以省略低阶项与首项系数，例如一个函数的执行次数为 n^2 + n^3，我们可省略 n^2，其时间复杂度为 O(n^3)。
private int test(){
for(int i = 0; i < n; i++){ //此处会执行n+1次
System.out.println("Hello World!"); //此处会执行n次
}
return 1; //此处会执行1次
}
常见时间复杂度（以下复杂度以升序排列）
- 常数复杂度：O(1)
- 对数复杂度：O(log n)
- 常数对数阶：O(n log n)
- 线性时间复杂度：O(n)
- 平方：O(n^2)
- 立方：O(n^3)
- 指数：O(2^n)
- 阶乘：O(n!)
此图来自“极客时间”
代码示例
- O(1)：
int i = 0;
System.out.println(String.valueOf(i));
System.out.println("one");
- O(log n)：
//由于在循环x次之后，i将大于或等于n跳出循环，即 2^x = n，x = logn，所以时间复杂度为O(logn)
for(int i = 0; i < n; i ++){
i *= 2;
System.out.println("i = " + i);
}
- O(n log n)：
for(int i = 0; i < n; i++){
while(i <= n){
i = i * 2;
System.out.println("i = " + i);
}
}
- O(n)：
for(int i = 0; i < n; i++){
System.out.println("i = " + i);
}
- O(n^2)：
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
System.out.println("i = " + i + “ ”+ “j = ” + j);
}
}
- O(n ^3)：
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
for(int k = 0; k < n; k++){
System.out.println("i = " + i + “ ”+ “j = ” + j + “ ”+ “k = ” + k);
}
}
}
- O(2^n)：
for(int i = 0; i < Math.pow(2,n); i++){
System.out.println("i = " + i);
}
- O(n!)：
for(int i = 0; i < factorial(n); i++){
System.out.println("i = " + i);
}
public long factorial(long l) {
if (l <= 1) {
return l;
} else {
return l * factorial(l - 1);
}
}
空间复杂度计算示例
以下函数进行了两次内存分配，函数所占用的空间不会因为某个变量的变化而变化，也不存在循环，所以该函数的空间复杂度是一个常数，记做 O(1)，比较好理解。
private int test(){
int i = 1;
int j = 1;
i = 2;
j =3;
}
常见空间复杂度（以下复杂度以升序排列）
O(1)：以上示例即为 O(1)
O(n)：
private int test(){
int[] a = new int[n];
int i = 1;
int j = 1;
i = 2;
j =3;
}
- O(n^2)：
private int test(){
int[][] a = new int[n][n];
int i = 1;
int j = 1;
i = 2;
j =3;
}
