1.了解学习算法的目的,是一种编程的思想,以占最少的计算资源,最快的运行速度来书写代码。
算法的五大特征:
- 输入: 算法具有0个或多个输入
- 输出: 算法至少有1个或多个输出
- 有穷性: 算法在有限的步骤之后会自动结束而不会无限循环,并且每一个步骤可以在可接受的时间内完成
- 确定性:算法中的每一步都有确定的含义,不会出现二义性
- 可行性:算法的每一步都是可行的,也就是说每一步都能够执行有限的次数完成
2.算法效率衡量指标 ——时间复杂度
时间复杂度是对代码需要执行的步骤的总和的计算,对代码运行效率的一个衡量指标,记为T(n)
大O记法:不拘泥于常熟级别的差别,只考虑大量级的时间复杂度计数方法
时间复杂度计算时,一般指计算最坏时间复杂度
时间复杂度的计算规则:
- 基本操作,即只有常数项,认为其时间复杂度为O(1)
- 顺序结构,时间复杂度按加法进行计算
- 循环结构,时间复杂度按乘法进行计算
- 分支结构,时间复杂度取最大值
- 判断一个算法的效率时,往往只需要关注操作数量的最高次项,其它次要项和常数项可以忽略
- 在没有特殊说明时,我们所分析的算法的时间复杂度都是指最坏时间复杂度
常见的时间复杂度
执行次数函数举例 | 阶 | 非正式术语 |
---|---|---|
12 | O(1) | 常数阶 |
2n+3 | O(n) | 线性阶 |
3n2+2n+1 | O(n2) | 平方阶 |
5log2n+20 | O(logn) | 对数阶 |
2n+3nlog2n+19 | O(nlogn) | nlogn阶 |
6n3+2n2+3n+4 | O(n3) | 立方阶 |
2n | O(2n) | 指数阶 |
O(1) < O(logn) < O(n) < O(nlogn) < O(n2) < O(n3) < O(2n) < O(n!) < O(nn)
3.Python内置效率衡量工具——timeit
timeit.Timer(stmt = '函数',setup = '导入函数模块')
例子:timeit.Timer(stmt = 't1()',setup = 'from __main__ import t1')
衡量不同算法之间的效率
list内置操作的时间复杂度
dict内置操作的时间复杂度
4.数据结构
列表、字段、元组等均是Python内置的数据结构,在书写代码时,数据结构是数据的载体,是数据的保存形式。通过算法的思想编程,利用数据结构的载体承载数据,最后才能完成一个程序。
根据不同的数据类型采用相对应的数据结构可以最小化数据运算的时间复杂度
抽象数据类型:给一个数据结构以及对应运算整合到一起,类似于根据某个数据写了一个类,里面有增删改查等功能
数据运算:插入、删除、修改、查找、排序
拜师教育学员文章:作者:2707-小吴同学,
转载或复制请以 超链接形式 并注明出处 拜师资源博客。
原文地址:《数据结构与算法Day1》 发布于2022-01-27
评论 抢沙发