P 数据结构 | 算法与数据结构

2019-10-03 本文已影响0人 Ricsy

一、算法

1.1 算法

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

eg:

C++描述、Python描述

1.1.1 算法的五大特性

算法的五大特性	描述
输入	算法有0个或多个输入
输出	算法至少有一个输出
有穷性	算法在有限步骤之后会自动结束而不会无限循环，并且每一个步骤可以在可接受的时间内完成
确定性	算法的每一步都有确定的含义，不会出现二义性
可行性	算法的每一步都是可行的，也就是说算法的每一步能够执行有限的次数完成

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

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. 反映的是最乐观最理想的情况，价值不大，
最坏时间复杂度 `常用`	算法完成工作最多需要多少基本操作 1. 提供一种保证，表明算法在此种程度的基本操作中一定能够完成工作
平均时间复杂度	算法完成工作平均需要多少基本操作 1.对算法一个全面的评价，但衡量没有保证，不是每个计算都能够在基本操作中完成，也会因为算法的实例分布可能并不均匀而难以计算

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

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

基本计算规则	描述
基本操作	即只有几个常数项，O(1)
顺序结构	时间复杂度按加法计算
循环结构	时间复杂度按乘法计算
分支结构	时间复杂度最大值 eg: 由于程序执行`if-elif-else`时，只会选择基本的三个分支的一个去执行，所以选取三个分支的时间复杂度的最大值即可

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

2. 常见的时间复杂度

执行次数函数示例	阶	非正式语
$12$	O( $1$ )	常数阶
$5log_2n+12$	O( $logn$ )	对数阶
$2n+12$	O( $n$ )	线性阶
$2n+5nlogn+12$	O( $nlogn$ )	$nlogn$ 阶
$3n^2+2n+12$	O( $n^2$ )	平方阶
$6n^3+3n^2+2n+12$	O( $n^3$ )	立方阶
$2^n$	O( $2^n$ )	指数阶
$n!$	O( $n!$ )	阶乘阶
$n^n$	O( $n^n$ )

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

提示：

$log_2n$ 简写为 $logn$

3. Python内置类型性能分析

(1) timeit模块

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

import timeit


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

参数	说明
`Timer`	测试小段代码执行速度的类
`stmt`	要测试的代码语句（statment）
`setup`	运行代码时需要的设置
`timer`	Timer()中其他参数 1. 定时器函数，与平台有关
`timeit()`	Timer类中测试语句的执行速度的对象方法
`number`	测试代码时的测试次数，默认一百万次
`avg_res`	执行代码的平均耗时 1. 数据类型：float类型 2. 单位：秒

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

(2) 应用

eg：

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

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

my_list.append()和my_list.insert()
[] + []
[x for x in range(10000)]
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 数据结构

重要概念	描述
数据	它是一个抽象的概念，将其进行分类后得到程序设计语言中的基本数据类型（只保存一个数据）
结构	就是各数据元素之间存在的特定关系
数据结构	指数据对象中数据元素之间的关系 Python的内置数据结构：不需要我们去定义的数据结构，如：列表、元组、字典等 Python的扩展数据结构：需要自定义实现这些数据的组织方式，如栈、队列等

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

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

名称	描述
数据结构	数据结构只是静态地描述了数据元素之间的关系数据结构是算法需要处理的问题载体
算法	为了解决实际问题而设计的
程序	高效地程序需要在数据结构的基础上设计和选择算法

程序 = 数据结构 + 算法

3.1 抽象数据类型

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

常用数据运算	描述
插入
删除
修改
查找
排序

更新中......