数据结构第一课 —— 时间和空间复杂度
目录
- 一、什么是数据结构？
- 二、关于算法的好坏
- 1、算法效率
- 三、时间复杂度
- 1、时间复杂度是什么？
- 2、关于大O表示法
- （1）大O的渐进表示法
- （2）大O阶方法的推导
- 四、空间复杂度
- 空间复杂度是什么？
一、什么是数据结构？
要想学好数据结构，我们首先要知道数据结构是什么？
在百度搜索中，我们可以找到这个问题的答案：数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。
二、关于算法的好坏
在了解什么是数据结构后，我们再来思考一个问题：我们如何来评断一个算法的好坏？
是通过算法运行的时间还是通过算法开辟的空间？究竟是时间更为重要还是空间更为重要呐？
下面，我们就来解答这个问题。
1、算法效率
算法的效率分为两种：一是时间效率，二是空间效率。其中，时间效率被称为时间复杂度；同样的，空间效率被称为空间复杂度。
时间复杂度：主要用来衡量一个算法的运行速度。
空间复杂度：主要用来衡量一个算法所需要的额外空间。
虽然两种效率所衡量的对象不同，但是，两种效率对于算法来说都很重要，但在目前来说，对于一个算法评断它的好坏时：时间复杂度>>空间复杂度。
三、时间复杂度
1、时间复杂度是什么？
首先，我们来了解一下什么是时间复杂度。
时间复杂度：在计算机科学中，时间复杂性，又称时间复杂度，算法的时间复杂度是一个函数，它定性描述该算法的运行时间。
简单来说：算法中基本操作的执行次数，为该算法的时间复杂度。
2、关于大O表示法
（1）大O的渐进表示法
要想计算某算法的时间复杂度，首先要学会大O表示法。
首先举个例子：
public class Test {
public static void main(String[] args) {
int count=0;
for (int i = 0; i < N; i++) {
count++;
}
}
}
如果说要计算上面算法的时间复杂度。
我们知道，count=0; int i=0;这两部分是只进行一次的。所以对于这两部分来说，一共是2个时间单元。
在i<N部分一共是N+1个时间单元（在最后一次还要比较一下）。
在i++和count++部分一共是2*N个时间单元。
那么，这个算法一共需要3*N+3个时间单元。
| N | 1 | 1000 |
|---|---|---|
| 3*N+3 | 6 | 30003 |
| 3*N | 9 | 30000 |
| N | 1 | 10000 |
由上表，我们可以看出，对于N很大的情况下，常数对我们的时间复杂度影响不大。然而，当N变大的情况下，N前的系数对于时间复杂度的影响也渐渐减小了。
所以，我们这时提出大O表示法：
大O符号：是用于描述函数渐进行为的数学符号。
（2）大O阶方法的推导
1、用常数1取代运行时间中的所有加法常数。
2、在修改后的运行次数函数中，只保留最高阶项。
3、如果最高阶项存在且不是1，则去除与这个项目相乘的常数，得到的结果就是大O阶。
当然，在某些算法的时间复杂度存在最好、平均和最坏的情况。
最好情况：任意输入规模的最小运行次数（下限）。
平均情况：任意输入规模的期望运行次数。
最坏情况：任意输入规模的最大运行次数（上限）。
在实际情况中，我们关注的一般是算法的最坏情况。
四、空间复杂度
空间复杂度是什么？
空间复杂度(Space Complexity)是对一个算法在运行过程中临时占用存储空间大小的量度，记做S(n)=O(f(n))。
所以，空间复杂度算的是变量的个数。
当然，计算空间复杂度时，我们使用的也是大O渐进表示法。