一、时间复杂度为：
随着数据规模 的不断增大，以上
中的系数、低阶、常量对执行时间的增长趋势影响非常小。所以，可以写成：
这样，是近似得表达了程序的执行时间/执行性能。
二、对数阶时间复杂度
int i = 1;
for (;i <= n; i += i) {
System.out.print(i);
}
对上述代码进行分析：
第一次： ， 即
；
第二次： ， 即
；
第三次： ， 即
；
......
第次：
。
因为 ，所以
，得到：
。 最后得到：
。
下面我们再来看一段代码：
int i = 1;
for (;i <= n; i *= 3) {
System.out.print(i);
}
用相同的方法进行分析：
第一次： ， 即
；
第二次： ， 即
；
第三次： ， 即
；
第四次： ， 即
；
第五次： ， 即
；
......
第次：
。
因为 ，所以
，得到：
。 最后得到:
。
又因为: ，
， 其中常量
，
所以：。
以任何整数为底的对数阶的时间复杂度都是相等的：
三、常用时间复杂度排序
常数阶<对数阶<线性阶<线性对数阶<平方阶（立方阶，k次方阶）<指数阶<阶乘阶
| n=4 | n=10 | n=100 | n=10000 | n=1000000 | |
|---|---|---|---|---|---|
| O(1) | 1 | 1 | 1 | 1 | 1 |
| O(logn) | 0.60 | 1 | 2 | 4 | 6 |
| O(n) | 4 | 10 | 100 | 10000 | 1000000 |
O(logn)近似为O(1), 比O(n)要好很多。
- 注意：O(m+n)、 O(m*n)：m和n是表示两个数据规模。我们无法事先评估m和n谁的量级大，所以我们在表示复杂度的时候，就不能简单地利用加法法则，省略掉其中一个。
四、空间复杂度分析
public boolean contains(int[] arr, int target) {
for (int i = 0; i < arr.length - 1; i++) {
if (arr[i] == target) {
return true;
}
}
return false;
}
空间复杂度为 O(1)
public int[] arrayCopy(int[] arr) {
int[] newArray = new int[arr.length];
for (int i = 0; i < arr.length - 1; i++) {
newArray[i] = arr[i];
}
return newArray;
}
空间复杂度为 O(n)
常见的就这两种情况。
