python数据结构和算法「总结」

一。什么是算法

算法是计算机处理信息的本质，因为计算机程序本质上是一个算法来告诉计算机确切的步骤来执行一个指定的任务。一般地，当算法在处理信息时，会从输入设备或数据的存储地址读取数据，把结果写入输出设备或某个存储地址供以后再调用。

通俗的来讲，算法就是你解决问题的思路。

二。算法的五大特性

输入: 算法具有0个或多个输入

输出: 算法至少有1个或多个输出

有穷性: 算法在有限的步骤之后会自动结束而不会无限循环，并且每一个步骤可以在可接受的时间内完成

确定性：算法中的每一步都有确定的含义，不会出现二义性

可行性：算法的每一步都是可行的，也就是说每一步都能够执行有限的次数完成

三。时间复杂度

我们可以通过算法的执行来判断算法的优劣。但这个执行时间本身又收到程序执行环境（硬件）的影响。有没有什么可以客观的衡量算法的优劣呢？ ----------时间复杂度

我们假定计算机执行算法每一个基本操作的时间是固定的一个时间单位，那么有多少个基本操作就代表会花费多少时间单位。

每台机器执行的总时间不同，但同一算法执行的步骤数量在每台机器上是相同的。

时间复杂度可以用步骤的数量来表示，从而来表示算法的优劣

在计算时间复杂度时注意： N 问题的规模 走势的影响 数量级

- 算法的速度并非指时间，不是以秒为单位；而是操作数的增速。从增量的角度度量的。

- 平时说的算法的速度，指的是随着输入的增加，其运行时间将会以什么样的速度进行增加。

---------------------------------------------------------------------------------------------------

“大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)