时间空间复杂度分析

一、时间复杂度为：

$T(n) = 3n^2+3n+3$

随着数据规模 $n$ 的不断增大，以上 $T(n)$ 中的系数、低阶、常量对执行时间的增长趋势影响非常小。所以，可以写成：

$T(n)=O(n^2)$

这样，是近似得表达了程序的执行时间/执行性能。

二、对数阶时间复杂度

int i = 1;
for (;i <= n; i += i) {
    System.out.print(i);
}

对上述代码进行分析：

第一次： $i = 1$ ，即 $i = 2^0$ ；
第二次： $i = 2$ ，即 $i = 2^1$ ；
第三次： $i = 4$ ，即 $i = 2^2$ ；
......
第 $x$ 次： $i = 2^{x-1}$ 。

因为 $i <= n$ ，所以 $2^{x-1} <= n$ ，得到： $x = 1 + \log_2n$ 。最后得到： $T(n)=O(\log_2n)$ 。

下面我们再来看一段代码：

int i = 1;
for (;i <= n; i *= 3) {
    System.out.print(i);
}

用相同的方法进行分析：

第一次： $i = 1$ ，即 $i = 3^0$ ；
第二次： $i = 3$ ，即 $i = 3^1$ ；
第三次： $i = 9$ ，即 $i = 3^2$ ；
第四次： $i = 27$ ，即 $i = 3^3$ ；
第五次： $i = 81$ ，即 $i = 3^4$ ；
......
第 $x$ 次： $i = 3^{x-1}$ 。

因为 $i <= n$ ，所以 $3^{x-1} <= n$ ，得到： $x = 1 + \log_3n$ 。最后得到: $T(n)=O(\log_3n)$ 。

又因为: $log_3n = (\log_32) * (\log_2n)$ ，
$O(\log_3n) = O(C\log_2n)$ ，其中常量 $C= \log_32$ ，
所以： $O(\log_3n) = O(\log_2n)$ 。

以任何整数为底的对数阶的时间复杂度都是相等的： $O(\log_3n) = O(\log_2n)= O(\log_4n) = ......=O(\log_mn)$

三、常用时间复杂度排序

$O(1)<O(logn)<O(n)<O(nlogn)<O(n^2) <O(2^n)<O(n!)$

常数阶<对数阶<线性阶<线性对数阶<平方阶（立方阶，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)

常见的就这两种情况。