一、算法

1.1 算法

算法是独立存在的一种解决问题的方法和思想
算法可以用不同的语言进行描述实现

eg:

C++描述、Python描述

1.1.1 算法的五大特性

具有算法的五大特性的思路就可以称为算法

1.2 算法的时间效率

eg(算法的时间效率的引入):

a+b+c = 1000
a**2+b**2 = c**2

求出a,b,c可能的组合

• 单靠运行的时间来比较算法的优劣并不一定是客观准确的
  运行时间 = 基本运算总数*基本运算的单位时间= 时间单位*单位时间

提示：

• 时间单位对应基本操作数
• 基本单位的运行时间即单位时间离不开计算机环境（软件系统和硬件系统）

• 评价算法时需要忽略机器的环境而客观反映算法的时间效率即只考虑时间单位
• 考虑到实际价值，时间单位只看量级，不看常量因子
  示例：基于数学的函数曲线，第一象限中不管常量因子如何，n^3始终大于n^2

1.3 算法的复杂度

算法的时间复杂度 T(n)和空间复杂度 S(n)统称为算法的复杂度

1.3.1 时间复杂度

T(n)，n称为问题规模

• T(n) = a * n^m 近似于 O(n^m)（大O记法）
  所以以后提到时间复杂度，都是T(n)中最特征的部分O(n^m)，而不是整个T(n)

• 因此我们最关注的是算法的最坏情况，即最坏时间复杂度，是算法的保证

1. 时间复杂度的基本计算规则

• 判断一个算法的效率时，往往只看操作数量的最高次项，其他次要项和常数项可以忽略
• 没有特殊说明，算法的时间复杂度就是最坏时间复杂度

2. 常见的时间复杂度

执行次数函数示例	阶	非正式语
	O()	常数阶
	O()	对数阶
	O()	线性阶
	O()	阶
	O()	平方阶
	O()	立方阶
	O()	指数阶
	O()	阶乘阶
	O()

• 从上往下，时间复杂度越来越大

提示：

• 简写为

3. Python内置类型性能分析

(1) timeit模块

用来测试一小段python代码的执行速度

import timeit


timeit.Timer(stmt='pass', setup='pass')
# timeit()会重新开辟空间运行，即使用时需要导入含被测函数的包
avg_res = timeit.Timer.timeit(number=1000000)

• 启动文件
  当.py自启动时，其模块名应该是__main__
  当其他.py调用某.py时，调用的模块名应该是该.py的文件名

(2) 应用

eg：

列表：
内置操作的时间复杂度

定义列表的方式：
my_list = []

1. my_list.append()和my_list.insert()
2. [] + []
3. [x for x in range(10000)]
4. list(range(10000))

import timeit


def test_001():
    my_list = []
    for i in range(10000):
        my_list.append(i)


def test_002():
    my_list = []
    for i in range(10000):
        my_list = my_list + [i]


def test_003():
    my_list = [x for x in range(10000)]


def test_004():
    my_list = list(range(10000))


def test_005():
    my_list = []
    for i in range(10000):
        my_list.insert(0,i)


timer1 = timeit.Timer('test_001()', setup='from __main__ import test_001')
timer2 = timeit.Timer('test_002()', setup='from __main__ import test_002')
timer3 = timeit.Timer('test_003()', setup='from __main__ import test_003')
timer4 = timeit.Timer('test_004()', setup='from __main__ import test_004')
timer5 = timeit.Timer('test_005()', setup='from __main__ import test_005')
res1 = timer1.timeit(number=100)
res2 = timer2.timeit(number=100)
res3 = timer3.timeit(number=100)
res4 = timer4.timeit(number=100)
res5 = timer5.timeit(number=100)

print("append()：%.4f" % res1)
print("[] + []：%.4f" % res2)
print("[x for]：%.4f" % res3)
print("list()：%.4f" % res4)
print("insert()：%.4f" % res5)

结果：

append()：0.1225
[] + []：23.1820
[x for]：0.0504
list()：0.0303
insert()：3.0051

[]+[]> insert() > append() > [x for] > list()

字典：
内置操作的时间复杂度

1.3.2 空间复杂度

S(n)

• 定义为该算法消耗的存储空间，它是问题规模n的函数
• 是对一个算法在运行过程中临时占用存储空间大小的量度

二、数据结构

2.1 数据结构

• 不同的数据结构，数据存储方式不同，就会造成算法的时间复杂度不同

三、算法与数据结构的区别

• 程序 = 数据结构 + 算法

3.1 抽象数据类型

ADT （Abstract Data Type）
指一个数学模型以及定义在数学模型上的一组操作
即把数学类型和数学类型上的运算捆绑在一起进行封装

更新中......