数据结构与算法
基础数据结构
1.1数组
一个含有数据的列表
array = ["apples", "bananas", "cucumbers", "dates", "elderberries"]
了解某个数据结构(例如数组)的性能,得分析程序怎样操作这一数据结构。
一般数据结构有四种操作
- 读取 (查找数据中指定索引处的值, array[0])
- 查找 (从数据结构中找出某个数据值的所在)
- 插入
- 删除
重要理论:操作的速度,并不按时间计算,而是按步数计算
此外,操作的速度,也被成为称为 时间复杂度
每种操作所用的步数
- 读取:一步,计算机本身就有跳到任一索引位置的能力。
- 查找:从索引0处开始,一个一个去对比查找,这种也被称为
线性查找
,对于长度为 N 的数组,其线性查找的最多步数为 N- 插入:如果向数组的末尾插入,只需要一步,如果在开头或者中间插入,需要先将后边部分的数据一步一步向右挪,最后插入,所以需要额外的步数
- 删除: 看起来删除,只需要一步,但实际上,删除之后,需要将后面的数据往前挪,补齐删掉的地方。
1.2 集合: 一条规则决定性能
一种不允许元素重复的数据结构。
和数组相比,集合的查找与删除操作所需的步数是相同的,但对于插入,集合需要先确定是否存在值,因为它不能有重复的值
2.1 二分查找:对于有序数组的查找方法
对于从小到大排列的数组,从中间开始,比较所查找值的大小,如果小于中间值,则排除右侧,否则排除左侧
对于长度大的数据,二分查找比线性查找更具有优势
二风查找的大O记法为O(log N)
O(log N)
时间复杂度叫作对数时间
当数据量翻倍时,步数加1
大O记法
方便表达数据结构和算法的时间复杂度
不关注算法所用时间,只关注步数
忽略常数,在选择排序里面,效率实际上是O(N^2 / 2),但仍表示为O(N^2)
大 O 只保留最高阶的N
表示方法
如,数组不论多大,读取都只需 1 步。
表示为:O(1)
对于 N 个元素的数 组,线性查找需要花 N 步。
表示为:O(N)
线性时间与常数时间
O(N)也被称为线性时间。
O(1)被称为常数时间。
冒泡排序
1 | let array = [3, 13,2, 8, 4, 34, 53, 22] |
效率: O(N^2)
一般嵌套循环算法的效率就是 O(N^2)
选择排序
1 | let array = [9, 2, 6, 3, 1] |
效率为:O(N^2)
但选择排序比冒泡排序快一倍
插入排序
1 | let array = [2, 8, 3, 1, 5] |
- 标题: 数据结构与算法
- 作者: DansRoh
- 创建于 : 2024-05-13 00:00:00
- 更新于 : 2024-05-13 17:56:39
- 链接: https://blog.shinri.me/2024/05/13/26_数据结构与算法入门学习/
- 版权声明: 本文章采用 CC BY-NC-SA 4.0 进行许可。
评论