数据结构与算法 1-1 算法引入

本系列是我在学习《基于Python的数据结构》时候的笔记。本小节主要介绍什么是数据结构与算法并通过一个问题来引出算法，算法本质就是解决问题的思路。

一

什么是数据结构与算法？

如果将最终写好运行的程序比作战场，码农便是指挥作战的将军，而我们所写的代码便是士兵和兵器。

那么数据结构和算法就是~兵法！

如果没有兵法的话，不使用战略，可能会胜利也可能会失败。但是即便胜利，可能也会付出巨大的代价。但是如果有了兵法，可以大大的提高取胜的概率。类似的，如果我们在写代码的时候没有数据结构与算法的思想的话，照样能够写出代码，解决相应的任务，但是可能会面临很多问题，比如：

1. 如果没有看过数据结构与算法，在遇到一个问题的时候可能没有任何的思路，不知该如何下手去解决；
2. 如果没有看过数据结构与算法，虽然大部分时间可能解决了问题，可是对于程序运行效率和开销没有意识，导致程序的性能低下；
3. 如果没有看过数据结构与算法，在借助别人开发利器应用到自身的问题当中，遇到性能瓶颈的时候，不知道该如何进行针对性的优化。

因此，数据结构和算法是一名程序开发人员的必备基本功，不是一朝一夕就能练成绝世高手的。冰冻三尺非一日之寒，需要我们平时不断的主动去学习积累。

二

算法的提出

下面通过一道题来引入数据结构与算法：

如果 a + b + c = 1000，且a^2 + b^2 = c^2（其中a,b,c为自然数），如何求出所有a、b、c的可能组合？

如果不依靠数学公式的话，可以通过枚举法（一个数一个数来尝试）来求出所有的组合。

思路： a = 0, b = 0, c = 0， ... a = 1000, b = 1000, c = 1000。 看看上面的组合哪个组合满足题目的条件。当然此时将a + b + c = 2000，也是类似的，这是一类问题。

下面通过程序来实现上面的思路：

a = 0, b = 500, c = 500a = 200, b = 375, c = 425a = 375, b = 200, c = 425a = 500, b = 0, c = 500times = 208.44898915290833finished

算法就是刚刚在解决问题时候的思路，面对问题，该怎么去解决，怎么让计算机运行把这套题给解出来，这样的思路解决方法就是算法，也就是说计算的方法。下面引入算法的具体概念：

算法是计算机处理信息的本质，因为计算机程序本质上是一个算法来告诉计算机确切的步骤来执行一个指定的任务，也就是告诉计算机每一步做什么，相应的就是刚刚在解决问题时候整理的思路。一般地，当算法在处理信息时，会从输入设备或数据的存储地址读取数据，把结果写入输出设备或某个存储地址供以后再调用。

算法是独立存在的一种解决问题的方法和思想。独立存在的意思就是他不和实现程序的编程语言有关系，面对一个问题，思路有了，当然可以使用别的编程语言来实现，但是思路没有变，算法也就是思路是独立存在的。也就是说对于算法而言，实现的语言并不重要，重要的是思想。

算法的五大特征，也就是对解决问题的思路有几个要求或者几个特征：

1. 输入：算法具有0个或多个输入；
2. 输出：算法至少有1个或多个输出，算法最终是需要解决问题的，如果执行程序我们不关注结果，那么就没有任何意义了；
3. 有穷性：算法在有限步骤之后会自动结束而不会无限循环，并且每一个步骤可以在可接受的时间内完成；
4. 确定性：算法中每一步都有确定的含义，不会出现二义性。也就是说刚才针对问题的思路是确定的，不能够有二义性，不会让别人理解有差别；
5. 可行性：算法的每一步都是可行的，可以被编程语言实现，每一步都能够执行有限的次数完成。