0. 序言
虽然代码千差万别，但是常见的复杂度量级并不多。
如果你对简单的复杂度分析还不了解，建议先点击跳转阅读这篇文章：//www.greatytc.com/p/2d5e5f1bc77e
1. O(1)
O(1)只是常量级时间复杂度的一种表示方法，并不是指只执行了1行代码。比如以下代码,即便有3行，它的时间复杂度也是O(1)。
int i = 8;
int j = 6;
int sum = i + j;
因此：只要代码的执行时间不随n的增大而增大，这样代码的时间复杂度都记作O(1)，即便有成千上万行。
for(int i = 0;i<100000;i++){
i++
}
即便是循环，但是代码的执行时间不随n的增大而增大，所以这段代码的时间复杂度依然是O(1)
2. O(logn)、O(nlogn)
i=1; // 1
while (i <= n) { // 2
i = i * 2; // 3
}
代码1的时间复杂度是O(1),而代码2和代码3是循环代码，所以根据简单的时间复杂度分析办法，我们只关注循环执行次数最多的一段代码即可，因此这里我们关注代码2和3即可。我们先看下代码3：
i = i * 2; // 3
变量i从1开始取，每次循环都×2，当大于n时，循环结束。所以i的取值：
20、21、22、23......2x = n
所以我们只需要知道x的值，就知道代码3执行次数了。而为何最后“=n"呢，是因为i的最大可能值就是n。因此x的值就是x = log2n,所以这段代码的时间复杂度就是O(log2n)
i=1; // 1
while (i <= n) { //2
i = i * 3; // 3
}
从以上分析不难得出，这段代码的时间复杂度是O(log3n).而采用大O复杂度表示法的时候，可以忽略系数，因为不管是乘以3也好，还是乘以2也好，对变化趋势有影响的始终是n，所以代码3的时间复杂度用大O复杂度表示法表示为"对数阶O(logn)"，而根据时间复杂度分析方法之乘法法则：嵌套代码复杂度是嵌套内外代码复杂度的乘积，所以代码2和3这段代码的时间复杂度用大O复杂度表示法表示为"线性对数阶O(nlogn)"。而代码1的时间复杂度为O(1)，根据时间复杂度分析法之加法法则：总复杂度等于量级最大的那段代码的复杂度，所以以上两段代码的复杂度是"线性对数阶O(nlogn)"。
对时间复杂度分析法之加法法则和乘法法则不了解的，建议先点击跳转阅读这篇文章：//www.greatytc.com/p/2d5e5f1bc77e
3. O(m+n)、O(m * n)
int cal(int m, int n) {
int sum_1 = 0;
int i = 1;
for (; i < m; ++i) {
sum_1 = sum_1 + i;
}
int sum_2 = 0;
int j = 1;
for (; j < n; ++j) {
sum_2 = sum_2 + j;
}
return sum_1 + sum_2;
}
由于数据规模有两个，分别是m和n，而此时我们并不知道m和n谁的量级大，所以"复杂度分析法之加法法则（总复杂度等于量级最大的那段代码的复杂度）"失效，这段代码的时间复杂度是O(m+n).但是乘法法则依然有效：
int cal(int m, int n) {
int sum_1 = 0;
int i = 1;
int sum_2 = 0;
int j = 1;
for (; i < m; ++i) {
sum_1 = sum_1 + i;
for (; j < n; ++j) {
sum_2 = sum_2 + j;
}
}
return sum_1 + sum_2;
}
通过上面的分析，不难得出，这段代码的时间复杂度是O(m * n)。
4. 后续
如果大家喜欢这篇文章，欢迎点赞！
如果想看更多 数据结构 方面的文章，欢迎关注!
