✨hello，进来的小伙伴们，你们好呐！✨
🌯🌯系列专栏：【数据结构与算法】
🍗🍗本篇内容：夯实基础——认识时间复杂度和空间复杂度！
🥞🥞作者简介：双非本科大三在读的一名Java初学者，星夜漫长，你我同行！
一、算法效率
🥭🥭衡量一个算法好坏的标准可以从这个算法的运行速度和所需的内存空间两个角度来分析，那么这两个因素哪个究竟是优先考虑的呢？
🍄🍄即时间效率被称为时间复杂度，而空间效率被称作空间复杂度。 时间复杂度主要衡量的是一个算法的运行速度，而空间复杂度主要衡量一个算法所需要的额外空间。
一、时间复杂度
🥠🥠定义：算法中的基本操作的执行次数，为算法的时间复杂度。
下面我将通过几个实例来演示如何计算一个算法的时间复杂度。
🚤🚤1.大O的渐进表示法
大O符号（Big O notation）：是用于描述函数渐进行为的数学符号。
🛰️🛰️推导大O阶方法：
1、用常数1取代运行时间中的所有加法常数。
2、在修改后的运行次数函数中，只保留最高阶项。
3、如果最高阶项存在且不是1，则去除与这个项目相乘的常数。得到的结果就是大O阶。
好了，那么知道了推导方法，我们看下面这个实例：
请计算一下func1基本操作执行了多少次？
void func1(int N){
int count = 0;
for (int i = 0; i < N ; i++) {
for (int j = 0; j < N ; j++) {
count++;
}
}
for (int k = 0; k < 2 * N ; k++) {
count++;
}
int M = 10;
while ((M--) > 0) {
count++;
}
System.out.println(count);
}
🍼🍼解答：
我们可以看到fun（）函数里面开头是双层循环，先看最里面的j从0遍历到n-1共循环了N次，那么每循环一个j，外层循环i就会循环n次，也就是说循环了n*n次，也就是计算了n^2次,所以执行的基本操作次数n^2；接着看我们的K，因为k是小于2*n的，所以这部分代码执行的基本操作次数就是2*n；最后while（m--），因为M的值是10，所以执行的基本操作次数是10，加起来是n^2+2*n+10；
再根据上面的推导大O阶方法，常数用1取代，那么m就为1；又因为保留最高阶项，所以去掉我们的2*n；因为我们的最高阶项系数是1，所以最后得到的结果是n^2+1，那么我们可以想象一下，当n足够大时，这个1还有保留的必要吗？显然，我们可以省去1，那么func1()的时间复杂度就是O(n^2)；🍬🍬
🍖🍖结论：大O的渐进表示法去掉了那些对结果影响不大的项，简洁明了的表示出了执行次数。
另外有些算法的时间复杂度存在最好、平均和最坏情况：
最坏情况：任意输入规模的最大运行次数(上界)
平均情况：任意输入规模的期望运行次数
最好情况：任意输入规模的最小运行次数(下界)
✈️✈️在实际中一般情况关注的是算法的最坏运行情况！
实例2：
计算func3的时间复杂度？
void func3(int N, int M) {
int count = 0;
for (int k = 0; k < M; k++) {
count++;
}
for (int k = 0; k < N ; k++) {
count++;
}
System.out.println(count);
⛵⛵解答：
可以看到，fun3是由两个循环来组成，所以基本语句的执行次数就是M+N，由于M和N是未知的，所以时间复杂度为O（M+N）。
实例3
计算fun4的时间复杂度？
void func4(int N) {
int count = 0;
for (int k = 0; k < 100; k++) {
count++;
}
System.out.println(count);
}
🚀🚀解答：
这一题猛一看上去就是 O（100）嘛，没的说，这么简单，其实从理论上来说没有问题的，因为基本操作执行了100次，但是根据我们的大O推导法，这里的100是常数项，那么时间复杂度就是O（1）。
下面我们来看几个难度升级的例子！
