数据结构第一章：概念与引入

引入

题目：如果 a+b+c=1000，且 a^2 + b^2=c^2（a,b,c 为自然数），如何求出 a,b,c 可能的组合？

---

方法一：枚举法

a:0----->10000
    b: 0----->1000
        c:0----->1000
            if a+b+c==1000 and a**2 + b**2 == c**2:
                print(a,b,c)

这样枚举的耗时约 244 秒，非常浪费时间·，于是我们需要调整我们的计算方法来优化这个程序。

算法的五大特性

1. 输入：有 0 个或者多个输入；
2. 输出：至少有 1 个或多个输出；
3. 有穷性：需要在有限的步骤之后运行完成而非无限循环；每一个步骤要在可接受的时间范围之内完成；
4. 确定性：每一个步骤都要有确定的含义；
5. 可行性：每一步都能够被有限次数地执行。

改进 ：将 c 优化

a:0----->10000
    b: 0----->1000
        c= 1000-a-b
        if a**2 + b**2 == c**2:
            print(a,b,c)

这样枚举耗时 1 秒，有明显的改进。

改进后的程序和改进前的程序执行的步骤不一样，改进前明显运算更多。

可见，解决同一个问题，不同的算法耗费的时间和资源是不同的，那么我们该如何评价一个算法的好坏呢？

时间复杂度与“大 O 记法”

假定每执行一个基本运算所消耗的时间为一个固定时间单位，那么有多少个基本运算就代表有多少个时间单位，一个程序执行的基本运算数量便可以称之为时间复杂度。

对于一开始的枚举法：

基本运算的数量为 100010001000*2=T，

那么如果 a+b+c=N，T=NNN*2，

那就可以说，对于该算法，其时间复杂度 T(N) = n^3 * 2。

在分析一个问题的时候，我们可以忽略系数，只需要关心数量级，那么 T(N)=n^3，就可以称这个为_ O(N)。_

最坏时间复杂度

在改进后的算法中，O(N)=N^2。

假设说，这个 N 很凑巧，我们的程序只执行了 N 边以内就解决了问题，并退出程序，他的时间复杂度就达不到 N^2，这个时候 O(N)=N 就是最优时间复杂度，而 O(N)=N^2 就是最坏时间复杂度。

而我们在计算时间复杂度的时候，只考虑最坏的情况，也就是 O(N)=N^2。

时间复杂度的基本计算

1. 基本运算+_*/bool，即使只有常数项，也认为其时间复杂度为 O(1)；
2. 顺序结构，按加法运算；
3. 循环结构，按乘法运算；
4. 分支结构，取分支时间复杂度的最大值；
5. 判断一个算法效率时，只关注数量级，系数、常数项可以忽略，也就是侧重循环结构；
6. 判断一个算法的时间复杂度，一般取最坏时间复杂度。

常见时间复杂度

执行次数函数	阶数	非正式术语
2	O(1)	常数阶
123n+12	O(n)	线性阶
n^2+2n+12	O(n^2)	平方阶
5log2(n)+12	O(log(n))	对数阶
2n+3nlog2(n)+12	O(nlog(n))	nlogn 阶
6n^3+3n^2+n+12	O(n^3)	立方阶
2^n	O(2^n)	指数阶

大小关系

1<log(n)<n<nlog(n)<n^2<n^3<2^n<n!<n^n

代码进行时间测量的模块 timeit

class timeit.Timer(stmt='pass',setup='pass',timer=<timer function>)

stmt 参数是要测试的代码语句；

setup 参数是要运行的代码时需要的设置；

timer 参数是一个定期函数，与平台有关。

from timeit import Timer
def test1()
    li = []
    for i in range(10000):
        li.append(i)

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

timer1 = Timer("test1()", "from __main__import test1")
timer2 = Timer("test2()", "from __main__import test2")
print(timer1.timeit{1000}) # 测算1000次

Python 中常用操作的复杂度

list

lst = list(range(10,20))
l1 = list(range(100,105))

操作	时间复杂度	描述
lst[2]	O(1)	访问元素
lst.pop()	O(1)	弹出最后一个值
lst.append(l1)	O(1)	在末尾添加元素
lst.extend(l1)	O(K)	在末尾逐个添加元素
lst.clear()	O(1)	清空list
lst.copy()	O(N)	列表拷贝
lst.count(15)	O(N)	元素计数
lst.remove(15)	O(N)	删除一个元素
lst.reverse()	O(N)	反序
lst.sort()	O(N*log(N))	排序
lst.insert(1,200)	O(N)	在某一位置插入元素
del lst[0]	O(N)	删除某个位置的元素
lst.index(15)	O(N)	查找元素，并返回元素位置
bisect.bisect_left(lst, 15)	O(log(N))	有序列表使用bisect查找元素

tuple

tpl = tuple(range(10))

操作	时间复杂度	描述
tpl[2]	O(1)	访问元素
tpl.count(2)	O(N)	元素计数
tpl.index(2)	O(N)	查找元素，并返回元素位置

set

ss1 = set(range(10))
ss2 = set(range(5,15))

操作	时间复杂度	描述
5 in ss1	O(1)	判断元素是否在set中
ss1	ss2	O(len(ss1)+len(ss2))
ss1 & ss2	O(len(s)*len(t))	取交集，等同于ss1.intersection(ss2)
ss1 - ss2	O(len(ss1))	取差集，等同于ss1.difference(ss2)
ss1 ^ ss2	O(len(ss1)*len(ss2))	取异或集，等同于
ss1.add(11)	O(1)	增加元素
ss1.pop()	O(1)	弹出一个元素
ss1.remove(5)	O(1)	删除指定元素

dict

dd = {'a':10,'b':20,'c':30,'d':40}

操作	时间复杂度	描述
dd[‘e’] = 50	O(1)	插入元素
dd[‘a’]	O(1)	访问元素，等同于dd.get(‘a’)
del dd[‘a’]	O(1)	删除元素
dd[‘b’] = 100	O(1)	修改元素
dd.pop(‘b’)	O(1)	弹出一个元素
dd.clear()	O(1)	清空字典

deque

from collections import deque
deq = deque(range(10))
ll = list(range(10))

操作	时间复杂度	描述
deq.pop()	O(1)	弹出最右侧的元素
deq.popleft()	O(1)	弹出最左侧的元素
deq.append(1)	O(1)	在右侧增加一个元素
deq.appendleft(1)	O(1)	在左侧增加一个元素
deq.extend(ll)	O(K)	在右侧逐个添加元素
deq.extendleft(ll)	O(K)	在左侧逐个添加元素
deq.rotate(K)	O(K)	旋转
deq.remove(5)	O(N)	删除指定元素
deq[0]	O(1)	访问第一个元素
deq[N-1]	O(1)	访问最后一个元素
deq[N/2]	O(N)	访问中间元素

数据结构

本质上是指如何把数据组合在一起，是对基本数据 int，float，str，char 的封装。

[
    ("zhangsan",23,"beijing"),
    ("zhangsan",23,"beijing"),
    ("zhangsan",23,"beijing"),
]
[
    {
    "name":"zhangsan",
    "age":23,
    "hometown":"beijing"
    },
]
{
    "zhangsan":{
        "age":23,
        "hometown":"beijing"
    }
}

程序 = 数据结构 + 算法

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

抽象数据类型

class test(object):
    def fun1()

    def fun2()

    def fun3()

不展示具体的数据类型和运算方法，只告诉封装好的数据使用方法，就是一个抽象的数据，它只能使用设定好的 def。

5 种常用数据运算：

1. 插入
2. 删除
3. 修改
4. 查找
5. 排序