第一章-初识数据结构

前言

什么是数据结构

数据结构(Data Structure)是计算机存储、组织数据的方式，指之间相互存在一种或特定关系的数据元素的集合。

什么是算法

算法是解决一类问题的一系列计算步骤。

数据结构和算法的重要性

笔试，面试必备。实际项目开发提供思想和思路，程序员的内功。

如何学好数据结构

1、疯狂写代码。

2、注意画图和思考。不懂得地方多画几遍图，思考出思路过后再用代码实现

3、多去在线OJ，推荐牛客网，和领扣网。

时间复杂度和空间复杂度

我们在实现一个算法之后应该如何来计算或者测量这个算法的优劣呢？这就要考虑到依靠算法的效率。效率分为时间效率和空间效率，但是我们该如何衡量这两大效率呢？因为每个计算机的性能都不一样，因此我们不能依靠在计算机上运行测试时间长短来计算效率，我们总不能把全世界的算法都放到同一台计算机上来进行测试。

因此我们为了更好的更方便的测试一个算法的效率就依靠数学计算来进行测量，由此诞生了时间复杂度和空间复杂度。

时间复杂度

时间复杂度在计算机科学中是一个数学函数，他基本代表了一个算法执行基本操作的次数。

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--)
    {
        ++count;
    }
    printf("%d\n", count);
}

像以上这这段代码我们可以用一个函数F(n)来计算其一次的执行次数，可得到F(n) = n ^ 2 + 2 * n + 10，但是这样表示过于复杂，也不够直观，由此我们引入了大O渐进表示法(Big O notation)，以下是大O渐进表示法的推导法则：

1、用常数1取代运行时间中的所有加法常数。

2、在修改后的运行次数函数中，只保留最高阶项。

3、如果最高阶项存在且不是1，则去除与这个项目相乘的常数。得到的结果就是大O阶。

有了这个方法我们可以将以上的F(n)表示为O(F(n)) = n ^ 2。对于这个阶级我们称之为平方阶，其时间效率是十分底下的，也是最为常见的。我们往往在使用了两个循环的时候就会出现平方阶。以下还有几个比较常见的阶级。

1、O(1)：常数阶。这个阶级是效率最为高效的，但也是可遇而不可求的。

2、O(logn)：对数阶。对数阶是效率次于常数阶的也是十分高效的阶级，也是我们平时所追求的算法的极致效率。

3、O(n)：线性阶。线性阶也是效率十分高效的了，并且也是十分常见的，同样的如果我们的算法不能达到对数阶那么也尽量应该达到线性阶

4、O(n ^ 2)：平方阶的效率比起以上的阶级效率上就要低下一些，但是在实战中并非所有的算法都能够达到前三大阶级，因此如果能达到平方阶我们则也可以称这个算法是好的，至少是有效的。

5、O(2 ^ n)：指数阶，这个阶级效率十分低下的效率，占用的时间增长十分的快，如果n的数值较小我们还是可以计算出结果的，但是n一旦稍微大一些，我们计算的时间往往过于漫长，因此一旦出现指数阶的算法我们是并不能将其投入使用的，这个算法也不能算是有效的。

空间复杂度

空间复杂度与时间复杂度类似，也采用大O渐进表示法，往往先计算出占单位空间的大小表达式，再进行化简表示。相比空间复杂度我们往往更加关注于时间复杂度，因为时间效率往往是优先的。有的情况下我们不得不做出舍弃空间减少时间的决策，同样的也会做出舍弃时间减少空间的决策，这都要根据具体场景来进行决定。