[数据结构与算法]数据结构与算法

数据结构与算法：解决问题的思路和方法。相当于战争中的“兵法”，在面对新问题的时候能帮助提供思路。

算法特性：

有输入、有输出、有穷性（非无限循环、运行时间可接受）、确定性（无二义）、可行性

算法效率衡量：

1.运行时间：不一定是客观准确的，要结合实现环境。

2.时间复杂度：基本运算的数量，也就是执行的步骤数量总和。通常主要关注最坏时间复杂度，也就是说最坏需要多少步，一定能完成。

两个函数若只有系数或常量的区别（例如：F(n)=3*n^3，G(n)=n^3，n是所处理问题的规模），则G(n)是F(n)的渐进函数。则G(n)就叫做该时间复杂度的大O表示法。也就是最能体现变化趋势特征的函数。（只要特征，别的不要。）

时间复杂度的计算原则（通常计算最坏时间复杂度）：

1.基本操作：认为只有常数项认为是1

2.顺序：按加法算

3.条件判断：按最大值（按判断后进行步骤多的走）

4.循环：按乘法算（次要项和常数项忽略，只保留最高次数项）

时间复杂度比较：O(1)<O(logn)<O(n)<O(nlogn)<O(n^2)<O(n^3)<O(2^n)<O(n!)<O(n^n)

数据结构：数据的保存形式

程序 = 数据结构+算法

抽象数据类型：

数学模型--数据怎么保存（例：定义一个类）+在此数学模型上的操作方法（例：类里面的方法）