【数据结构】（一）：基础知识

一、算法效率衡量

时间复杂度

假设存在函数g，是的算法A处理规模为n的问题所用的时间为T（n）=O(g(n))，则称O（g(n)）为算法A的渐进时间复杂度，简称时间复杂度。

最坏时间复杂度

算法完成工作最多需要多少基本操作，即最坏时间复杂度
最坏时间复杂度提供了一种保证，表明算法在此种程度上的基本操作中一定能完成工作。

时间复杂度的几条基本计算规则

1. 基本操作，只有常数项，认为其时间复杂度为O（1）。
2. 顺序结构，时间复杂度按加法进行计算。
3. 循环结构，时间复杂度按乘法进行计算。
4. 分支结构，时间复杂度取最大值。
5. 只关注操作数量的最高次项，其他次要项和常数项可以忽略。

常见时间复杂度

所消耗的时间大小：O(1)<O(logn)<O(n)<(nlogn)<O(n^2)<O(n3)<O(2的n次方)<O(n!)<O(n的n次方)

二、数据结构

我们怎么用python中的类型保存一个班的信息？
答：可以用列表、字典、元组等python中已封装好的数据结构来保存。
举例

'''
用python中的数据结构保存一个班的学生信息

name
age
hometown

可以用列表、字典、元组
'''
# 1、列表+元组
[
   ("zhangsan",21,"beijing"),
   ("lisi",22,"nanjing"),
   ("wangwu",24,"dongjing")
]

# 2、列表+字典
[
   {
      "name":"zhangsan",
      "age":21,
      "hometown":beijing
   },
   {
      ...
   }
]

# 3、字典+字典
{
   "zhangsan":{
      "age":21,
      "hometown":"beijing"
   },
   "lisi":{
      "age":22,
      "hometown":"nanjing"
   },
   "wangwu":{
      ...
   }
}

以上三种方法，用列表时，想在列表中获得一名同学的信息时，其复杂度为O（n）,而用字典时，其复杂度为O(1)。

算法与数据结构

数据结构只是静态的描述了数据元素之间的关系。
高效的程序需要在数据结构的基础上设计和选择算法。
程序=数据结构+算法

抽象数据类型（Abstract Data Type）

把数据类型即数据类型上的运算捆在一起，进行封装。
常用的数据运算有五种：

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