《数据结构与算法》第二课：算法

Bo主前言：
自清明以来，Bo主是感冒发烧头痛牙疼，所以一直拖到现在才发第二课。第二课相比第一课概念的东西少很多，主要介绍了算法、算法的时间复杂度和算法的空间复杂度的概念以及计算方法，掌握此篇博客的内容有利于日后解决相关的计算题，所以加油吧！还有就是，注意身体。

在《数据结构与算法》这门学科中，由学科题目就可以看出数据结构与算法是不可分割的，是同等重要的。

在许多大牛的博客和书中都会提到一句话：若把数据结构比喻成肉体，算法则是灵魂。

由此可见，算法的重要性不言自明！

那么，算法到底是什么呢？我们该如何才能学好算法呢？

2.1 算法是什么？

算法这个词，对于大多数非计算机专业人员来说还是挺陌生的。就像我在没上专业课之前，也没听说过算法一词，不过其实早在小学甚至更早，我们就已经运用到了算法的概念，只是当时不是以算法一词来称谓。

小学的时候，数学老师常说要试着用不同的解题思路来解决同一个问题，这里的解题思路其实就是算法。

算法，即解决问题的方法。

解决上班交通问题，我们可以采用乘坐出租车，乘坐大巴车，乘坐私家车等方式，当然为了响应国家低碳生活的号召，也可以选择走路。

在这里，我们用了不同的方式来解决上班交通问题，那么对于不同的方式，有什么优缺点呢？

这里就涉及到了算法比较的问题。

我们就拿乘坐出租车和乘坐大巴车来做比较。乘坐出租车通常会比大巴车更快到底目的地，但出租车的费用通常也会比大巴车要高。所以，对于不同的算法，并没有完美的可以兼顾所有问题的算法，只是根据你的侧重点来选择，若更加侧重效率，你可以选择乘坐出租车的方式；若更加侧重金钱，你也可以选择乘坐大巴车的方式。

2.2 算法的时间复杂度

在进行算法分析和比较时，通常将算法的时间复杂度和算法的空间复杂度作为评阶标准。

算法的时间复杂度：即随着问题规模的增大，算法执行时间的增长规模。

如何计算算法的时间复杂度，在对算法的事前分析预估和研究生入学考试都是相当重要的。

在这里，我们采用推导大O阶方法来计算算法的时间复杂度。

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

由此，我们得到了一个计算算法时间复杂度的万能公式，可是在计算时间复杂度时，可没这么简单。

当问题的规模增大时，算法的时间复杂度通常被分为

1. 常数阶：O(1)
2. 线性阶：O(n)
3. 对数阶：O(logn)
4. 平方阶：O(n^2)
5. 指数阶：O(2^n)

常用的时间复杂度所消耗的时间从小到大依次是：

O(1)<O(n)<O(logn)<O(n^2)<O(2^n)<O(n^n)

算法的空间复杂度通过计算算法所需要的存储空间实现。算法执行期间所需要的存储空间包括3部分：

1. 算法程序所占的空间
2. 输入的初始数据所占的存储空间
3. 算法执行过程中所需要的额外的空间

通常，我们都使用‘时间复杂度’来指运行时间的需求，使用‘空间复杂度’来指空间需求。

当不限定的用‘复杂度’时，通常指时间复杂度。