java时间复杂度计算个人笔记

时间复杂度是指算法执行语句执行的次数。
常见的时间复杂度有以下几种：

描述	时间复杂度
常数阶	O(1)
对数阶	O(logn)
线性阶	O(n)
线性对数阶	O(nlogn)
平方阶	O(n2)
立方阶	O(n3)
n次方阶	O(m?)
指数阶	O(2?)
阶乘阶	O(n!)

(1) O(1) O(1)是常量级时间复杂度的一种表示方法，并非只执行一行代码。
代码执行时间不是随着n的增大而增大，这样的代码的时间复杂度都是O(1)。
注意：通常只要算法中不存在循环、递归，即使代码有很多行，时间复杂度仍是O(1)
(2) O(logn)、O(nlogn)对数阶时间复杂度

int i = 1; while(i<=n){ i=i*2; }

代码line3是执行次数最多的，只要算出第3行执行的次数，它代表的就是整个代码的时间复杂度。i从1开始取值，每一次循环乘以2。可以看到 i=i*2是一个等比数列，即：2o 2122 ...... 2^k = n。只要算出k是多少，就是执行的次数了2^k=n -->k=log2n，所以时间复杂度应该为O(log2n)。

int i = 1; while(i<=n){ i=i*5; }

很容易就能看出来，应该是O(log5n)。但是上面的O(log2n)和O(log5n)可以通过换底公式换成以2为底的对数，且可以忽略系数，所以都记做 O(logn)。
关于O(nlogn),就是把上面的代码在循环执行n遍了。其中归并排序、快速排序的时间复杂度就是O(nlogn)
（3）O(m+n)、O(m*n) 1. 加法法则（量级最大法则）：总复杂度等于量级最大的那段代码的复杂度。

public static Integer getSum(Integer n){ int sum1 = 0; int sum2 = 0; for (int i = 0; i < 1000; i++){ sum1 += i; }for (int i = 0; i < n; i++){ for (int j = 0; j < n; j++){ sum2 += i*j; } }return sum1 + sum2; }

sum1和sum2分别是 O(n)和O(n2)，对于这三个，我们取量级最大的O(n2)，所以总的时间复杂度就等于量级最大的那段代码的时间复杂度。
【java时间复杂度计算】2.乘法法则：嵌套代码的复杂度等于嵌套内外代码复杂度的乘积。

public static Integer getSum(Integer n){ int sum = 0; for (int i = 0; i < n; i++){ sum += func(i); }return sum; }publicstatic Integer func(Integer x){ int sum = 0; for (int i = 0; i < x; i++){ sum += i^2; } return sum; }

func()函数的时间复杂度是 T1(n)=O(n)，如果先把func()函数看成简单的操作，则getSum()函数的时间复杂度是T2(n)=O(n)，所以整个getSum()函数的时间复杂度是T(n)=T2(n)*T1(n)=O(n*n)=O(n^2)
3.循环不仅与n有关，还与执行循环所满足的判断条件有关。