数据结构
数据结构与算法
· ☕ 3 min read
基本概念 什么是数据结构? 数据结构是相互之间存在一种或多种特定关系的数据元素的集合。 数据结构是一门研究非数值计算的程序设计问题中的操作对象,以及它们之间的关系和操作等相关问题的科学。 逻辑结构 逻辑结构,是指数据对象中数据元素之间的相互关系。 类型 说明 数据结构 集合结构 集合结构中的元素除了同属于一个集合外,它们之间没有其它关系。 链表、Set 线性结构 线性结构中的元素之间是一对一的关系。 串、数组、链表、栈、队列、哈希 树型结构 属性结构中的元素之间存在一种一对多的层次关系。 树 图形结构 图形结构的数据元素是多对多的关系。 图 物理结构 物理结构,是指数据的逻辑结构在计算机中的存储形式。 类型 说明 顺序存储结构 是把数据元素存放在地址连续的存储单元里,其数据间的逻辑关系和物理关系是一致的。 链接存储结构 把数据元素存放在任意的存储单元里,这组存储单元可以是连续的,也可以是不连续的。 数据元素的存储关系并不能反映其逻辑关系,因此需要用一个指针存放数据元素的地址,这样通过地址就可以找到相关联数据元素的位置。 算法时间复杂度 在进行算法分析时,语句总的执行次数T(n)是关于问题规模n的函数,进而分析T(n)随n的变化情况并确定T(n)的数量级。 算法的时间复杂度,也就是算法的时间量度,记作:T(n) = O(f(n))。 它表示随问题规模n的增大,算法执行时间的增长量和f(n)的增长率相同,称作算法的渐进时间复杂度,简称为时间复杂度。 其中f(n)是问题规模n的某个函数。 一般情况下,随着n增大,T(n)增长最慢的算法为最优算法。 常见的时间复杂度 执行次数函数 阶 非正式术语 排序 12 O(1) 常数阶 1 5log2n+20 O(logn) 对数阶 2 2n+3 O(n) 线性阶 3 2n+3log2n+19 O(nlogn) nlogn阶 4 3n2+2n+1 O(n2) 平方阶 5 6n3+2n2+3n+4 O(n3) 立方阶 6 2n O(2n) 指数阶 7 常用数据结构的时间复杂度 数据结构 时间复杂度 阶 哈希 O(1) 常数阶 树 O(log(n)) 对数阶 数组 O(n) 线性阶 链表 O(n) 线性阶 常用排序算法的时间复杂度 排序算法 时间复杂度(平均) 快速排序 O(n log(n)) 归并排序 O(n log(n)) 堆排序 O(n log(n)) 冒泡排序 O(n^2) 插入排序 O(n^2) 选择排序 O(n^2) 桶排序 O(n+k) 基数排序 O(nk) 数据结构图解 数组 链表 哈希 HashMap/HashTable ConcurrentHashMap 栈 队列 树 图 对比 数据结构 优点/特点 缺点 适用场景 数组 插入快,如果知道下标,可以非常快的存取 查找慢,删除慢,大小固定 数量固定的元素集合 有序数组 比无序数组查找快 删除和插入慢,大小固定 数量固定的有序元素集合 栈 提供后进先出方式的存取 存取其它项很慢 1.