1 数据结构与算法是什么？

看了一篇文章，感觉文章给出的比喻非常贴切。比如一场战争中，码农可以比作是战场上的将军，用的代码比作是小兵，那么数据结构与算法就是兵法！！！

我们可以不看兵法在战场上肉搏，如此，可能会胜利，可能会失败。即使胜利，可能也会付出巨大的代价。我们写程序亦然：没有看过数据结构和算法，有时面对问题可能会没有任何思路，不知如何下手去解决；大部分时间可能解决了问题，可是对程序运行的效率和开销没有意识，性能低下；有时会借助别人开发的利器暂时解决了问题，可是遇到性能瓶颈的时候，又不知该如何进行针对性的优化。因此，数据结构与算法，就是要让我们做到胸有成竹，掌握兵法，游刃有余地开展程序地编写，高效地实现代码运作！

所有代码是基于python3编写的。

2 数据结构与算法的研究问题？

2-1 引入

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

解法1：遍历所有

解法 1  时间复杂度为O(n**3)

因此我们可以看到，当算法以纯遍历的形式开展求解时，时间运行非常长。

解法2：少去一个循环

解法 2 时间复杂度为O(n**2)

可以看到，少了一个for循环，可以在一定程度上降低程序运行的时间。另外，我们都听说过内存这件事，因此我们往往希望能够在程序运行时缓存更少的数据空间，节约空间以便开展其它的并行任务！

总的来说，两个名词，时间复杂度与空间复杂度，就是我们所要研究的问题。

因此，数据结构与算法的五大特征先总结一下：

（1）输入，输入为0个以上；（2）输出，输出为1个以上；（3）有穷性，不能无限制的计算~；（4）确定性，不能输出有歧义的解；（5）可行性：算法编写的算法可以行的通的。

2-2  衡量算法的效率：

在2-1中，我们尝试了运用两种求解方法，最后运用一个时间来对比了我们的算法。但是需要指出的是，假设把解法1放在一个超级计算机上（比如天河号，乱猜的）所运行的时间可能要比解法2放在一个破笔记本电脑上的时间要短。那此时我们说解法1要比解法2高效，你觉得这样合理么？   显然，答案是否定的。   因此单靠时间来衡量算法的优劣显然是行不通的！！！   也就是说一个算法的求解是离不开计算机环境的硬件配置资源的。

（1）时间复杂度。以2-1中的解法1为例，a，b，c要分别遍历1001次，那么此时遍历完整个可能性解，是不是要 1001x1001x1001 次，这么多计算!  而解法2的话，对于for循环只需要遍历1001*1001次循环。可见两者足足差了约1001倍。

         因此我们以这种类似于循环次数作为研究对象，即假定程序每执行一次操作是一个时间单位，那么有多少次操作就代表其会花掉多少时间。对于算法的时间效率，我们可以用“大O记法”来表示。“大O记法”：对于单调的整数函数f，如果存在一个整数函数g和实常数c>0，使得对于充分大的n总有f(n)<=c*g(n)，就说函数g是f的一个渐近函数（忽略常数），记为f(n)=O(g(n))。也就是说，在趋向无穷的极限意义下，函数f的增长速度受到函数g的约束，亦即函数f与函数g的特征相似。时间复杂度：假设存在函数g，使得算法A处理规模为n的问题示例所用时间为T(n)=O(g(n))，则称O(g(n))为算法A的渐近时间复杂度，简称时间复杂度，记为T(n)。

         对于算法进行特别具体的细致分析虽然很好，但在实践中的实际价值有限。对于算法的时间性质和空间性质，最重要的是其数量级和趋势，这些是分析算法效率的主要部分。而计量算法基本操作数量的规模函数中那些常量因子可以忽略不计。例如，可以认为3n**2和100n**2属于同一个量级，如果两个算法处理同样规模实例的代价分别为这两个函数，就认为它们的效率“差不多”，都为n**2级。

（2）三个概念：  对于它们的理解，等将各种排序方法学完，就会有一个相对清晰地认知了。

         最坏时间复杂度：算法完成工作最多需要花费的基本操作；

         最优时间复杂度：算法完成工作最少需要花费的基本操作；

         平均时间复杂度：算法完成工作平均需要花费的基本操作；

（3）时间复杂度的几条基本规则：

         基本操作，即只有常数项，认为其时间复杂度为O(1)

        顺序结构，时间复杂度按加法进行计算

        循环结构，时间复杂度按乘法进行计算

        分支结构，时间复杂度取最大值

        判断一个算法的效率时，往往只需要关注操作数量的最高次项，其它次要项和常数项可以忽略

        在没有特殊说明时，我们所分析的算法的时间复杂度都是指最坏时间复杂度。 因此解法1的时间复杂度要比解法2 的时间复杂度大。

2-3 常见的时间复杂度

时间复杂度 统计表 时间复杂度大小的对比其它

3 其它

python中会用到list列表，list应该是一个顺序表，因此其时间复杂度如下：

list列表中的函数复杂度

    字典的复杂度

dict的复杂度

例子：实际上当我们在思考这个问题的时候，我们已经用到了数据结构。列表和字典都可以存储一个班的学生信息，但是想要在列表中获取一名同学的信息时，就要遍历这个列表，其时间复杂度为O(n)，而使用字典存储时，可将学生姓名作为字典的键，学生信息作为值，进而查询时不需要遍历便可快速获取到学生信息，其时间复杂度为O(1)。

因此回到我们的主题：数据结构与算法

        数据是一个抽象的概念，将其进行分类后得到程序设计语言中的基本类型。如：int，float，char等。数据元素之间不是独立的，存在特定的关系，这些关系便是结构。数据结构指数据对象中数据元素之间的关系。

        数据结构只是静态的描述了数据元素之间的关系。

        高效的程序需要在数据结构的基础上设计和选择算法。

        程序 = 数据结构 + 算法

        总结：算法是为了解决实际问题而设计的，数据结构是算法需要处理的问题载体

        常见的数据运算有五种：

        插入；删除；修改；查找；排序

参考链接：https://www.bilibili.com/video/av21540971?p=39