课程内容
数据结构和算法课程主要内容：
- 算法分析
- 基本结构（线性表、链表、栈和队列）
- 递归（递归算法和分治策略）
- 排序与查找
- 树及其算法
- 图及其算法
好算法评判标准：
1.需要的存储空间或内存少，或者可以重复利用存储空间
2.算法的执行时间少
time模块,获取当前时间，秒，是个浮点数，记录了从1970年1月1日00：00：00开始的
import time
time.time()
关于运行时间的实际检测，有点问题：与编程语言和运行环境有关
赋值语句少，执行的时间少
算法分析--数量级估算--大O数量级表示法 。
大O表示法，是时间复杂度的一种表示，当问题规模线性增长时，所需处理时间的增长趋势。
以空间换时间，时间和空间之间的取舍和权衡，在算法的选择和编程的设计经常存在。
什么是算法分析：
比较程序的“好坏”，有更多的因素：代码风格、可读性等等
我们主要感兴趣的是算法本身特性
算法分析主要就是从计算资源消耗的角度来评判和比较算法
更高效利用计算资源，或者更少占用计算资源的算法，就是好算法
所以从这个角度，前述两端程序实际上是基本相同的，它们都采用了一样的算法来解决累计求和问题
运行时间检测的分析
但关于运行时间的实际检测，有点问题：关于编程语言和运行环境
同一个算法，采用不同的编程语言编写，放在不同的机器上运行，得到的运行时间会不一样，有时候会大不一样：
比如把非迭代算法放在老旧机器上跑，甚至可能慢过新机器上的迭代算法
我们需要更好的方法方法来衡量算法运行时间
这个指标与具体的机器、程序、运行时段都无关
大O表示法：
算法时间度衡量指标
一个算法所实施的操作数量或步骤数可作为独立于具体程序/机器的度量指标
哪种操作跟算法的具体实现无关？
需要一种通用的基本操作来作为运行步骤的计量单位
问题规模影响算法执行时间
问题规模：影响算法执行时间的主要因素
在前n个整数累计求和的算法中，需要累计的整数个数合适作为问题规模的指标
前100000个整数求和对比前1000个整数求和，算是同一问题的更大规模。
算法分析的目标是要找出问题规模会怎么影响一个算法的执行时间
常见的大O数量级函数
通常当n较小时，难以确定其数量级
当n增长到较大时，容易看出其主要变化量级
| f(n) | 名称 |
|---|---|
| 1 | 常数 |
| log(n) | 对数 |
| n | 线性 |
| n*log(n) | 对数线性 |
| n^2 | 平方 |
| n^3 | 立方 |
| 2^n | 指数 |
用大白话来说：
对于一个算法，当要运算的输入数据量n变大时(问题规模变大)，它的运行时间随着数据量变大如何变化，
是随着n的增大，运行时间呈log(n)趋势增长，还是n^2趋势增长？
有辐图，看图理解。
世界上最早的算法：欧几里得算法
辗转相处法处理大数时非常高效
它需要的步骤不会超过较小数位数的5倍
Python 语言的实现中算法权衡
总的方案就是，让最常用的操作性能最好，牺牲不太常用的操作
80/20准则：80%的功能其适用率只有20%
在某些特殊应用里，算法的性能稳定也很重要。
字符串类型str和字节串类型bytes
python 语言中的字符串是Unicode字符的串
可以通过encode()方法转换为各种字符编码的字节串bytes 指定字符编码如gb2312,gbk等
而字节串则可以通过decode()方法转换为字符串str
字节串属于特定字符编码
unicode字符通过encode转为bytes特定编码的字节
bytes特定编码的字节通过decode转为unicode字符
type('中文')
# <class 'str'>
'中文'.encode()
# b'\xe4\xb8\xad\xe6\x96\x87'
'中文'.encode('gb2312')
# b'\xd6\xd0\xce\xc4'
type(b'\xd6\xd0')
# <class 'bytes'>
b'\xd6\xd0'.decode('gb2312')
# '中'
from big_o import big_o