[数据结构与算法]数据结构与算法（python）第一节

算法是计算机处理信息的本质，算法是独立存在的一种解决问题的方法和思想

算法五大特性：

（1）输入：有0个或者多个输入

（2）输出：至少有一个或多个输出

（3）有穷性：有限步骤后自动结束而不会无限循环，每一个步骤可以在可接受的时间内完成

（4）确定性：算法中每一步都有确定的含义，不能有二义性

（5）可行性：算法的每一步都能够用计算机语言实现

算法效率衡量 ：

执行时间

时间复杂度和大O记法

渐进函数 g(n） = n^3? ?O（g(n))? 渐进时间复杂度

时间复杂度

优先关注最坏时间复杂度

时间复杂度计算的几个基本原则：

（1）基本操作，只有常数项，时间复杂度是O（1）

（2）顺序结构，时间复杂度按加法计算

（3）循环结构，时间复杂度按乘法计算

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

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

（6）在没有特殊说明时，我们所分析的算法时间复杂度都是指最坏时间复杂度

常见时间复杂度

O(1) 常数阶

O(n) 线性

O(n^2) 平方阶

O(logn)对数阶

O(nlogn)?

O(n^3)

O(2^n) 指数阶

代码执行时间测量模块timeit

可以用来测试一小段Python代码的执行速度

Timer是测量小段代码执行速度的类

习惯? py文件起名的时候 文件名不要和包名 关键字名重合

举例练习，计算多种方式列表添加元素的运行时间：

from timeit import Timer
li1 = [1, 2]
li2 = [23, 5]

li = li1 + li2

li = [i for i in range(10000)]

#列表添加的四种方式
def test1():  #append()
    li = []
    for i in range(10000):
        li.append(i)

def test2():
    li = []
    for i in range(10000):
        li += [i]

def test3():
    li = [i for i in range(10000)]

def test4():
    li = list(range(10000))


timer1 = Timer("test1()", "from __main__ import test1")  #timer这个函数是在外部运行的，第二个参数是运行条件需要02list这个模块的，用__main__再模块内部用来标识模块名称
print("test1:", timer1.timeit(1000))

timer2 = Timer("test2()", "from __main__ import test2")  
print("test2:", timer2.timeit(1000))

timer3 = Timer("test3()", "from __main__ import test3")  
print("test3:", timer3.timeit(1000))

timer4 = Timer("test4()", "from __main__ import test4")  
print("test4:", timer4.timeit(1000))

四种方式运行时间结果：

test1: 0.333015125
test2: 0.379017417
test3: 0.15235016700000004
test4: 0.08127616599999998

数据结构

数据结构要解决的问题是数据如何组织起来，对基本数据类型的一种封装

程序 = 数据结构+ 算法

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

抽象数据类型 ：把数据类型和数据类型上的额运算捆在一起，形成一种封装

?