数据结构第一课 —— 时间和空间复杂度

一、什么是数据结构？

要想学好数据结构，我们首先要知道数据结构是什么？
在百度搜索中，我们可以找到这个问题的答案：数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。

二、关于算法的好坏

在了解什么是数据结构后，我们再来思考一个问题：我们如何来评断一个算法的好坏？
是通过算法运行的时间还是通过算法开辟的空间？究竟是时间更为重要还是空间更为重要呐？
下面，我们就来解答这个问题。

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++;
        }
    }
}
1
2
3
4
5
6
7
8

如果说要计算上面算法的时间复杂度。
我们知道，count=0; int i=0;这两部分是只进行一次的。所以对于这两部分来说，一共是2个时间单元。
在i一共是N+1个时间单元（在最后一次还要比较一下）。
在i++和count++部分一共是2*N个时间单元。
那么，这个算法一共需要3*N+3个时间单元。

由上表，我们可以看出，对于N很大的情况下，常数对我们的时间复杂度影响不大。然而，当N变大的情况下，N前的系数对于时间复杂度的影响也渐渐减小了。
所以，我们这时提出大O表示法：

大O符号：是用于描述函数渐进行为的数学符号。

（2）大O阶方法的推导

1、用常数1取代运行时间中的所有加法常数。
2、在修改后的运行次数函数中，只保留最高阶项。
3、如果最高阶项存在且不是1，则去除与这个项目相乘的常数，得到的结果就是大O阶。

当然，在某些算法的时间复杂度存在最好、平均和最坏的情况。
最好情况：任意输入规模的最小运行次数（下限）。
平均情况：任意输入规模的期望运行次数。
最坏情况：任意输入规模的最大运行次数（上限）。

在实际情况中，我们关注的一般是算法的最坏情况。

四、空间复杂度

空间复杂度是什么？

空间复杂度(Space Complexity)是对一个算法在运行过程中临时占用存储空间大小的量度，记做S(n)=O(f(n))。

所以，空间复杂度算的是变量的个数。

当然，计算空间复杂度时，我们使用的也是大O渐进表示法。