面试必备：数据结构时间复杂度及用法大全

<>基础数据结构

1.时间复杂度

数据结构根据索引查找根据关键字查找插入删除
数组(Array)O(1)O(n)O(n)O(n)
队列(queue)O(n)O(n)O(1)O(1)
链表(Linked list)O(n)O(n)O(1)O(1)
二叉树(Binary Search Tree) 平均情况O(log(n))O(log(n))O(log(n))
二叉树(Binary Search Tree) 最坏O(n)O(n)O(n))
2.空间复杂度

数据结构数组队列链表二叉树
空间复杂度O(1)O(1)O(1)O(1)
<>高级数据结构

数据结构各类操作时间复杂度能够解决哪些问题面试考察频率学习难度
堆(Heap)O(log(n)): push, pop; O(1):top全局动态找最大最小高低
哈希表(Hash table)O(1）: insert, find, delete查询元素是否存在，key-value查询问题高低
前缀树(Trip)O(1): insert, find, delete和哈希表解决问题类似，查询元素是否存在，key-value查询问题中低
并查集(UnionFind)O(1): union, find动态合并集合并判断两个元素是否在同一个集合中低
平衡排序二叉树(Balanced BST)O(log(n)): insert, find, delete, max, min, lower, upper
动态增删查改并支持找全局最大最小值； 找比某个数大的最小值和比某个数小的最大值可以用（尽可能接近）低高
跳跃表(Skip List)O(log(n)): insert, find, delete, max, min, lower, upper和Balanced
BST解决的问题一样，并能一直维持一个有序链表低高
树状数组(Binary Indexed Tree)O(log(n)): insert, delete, range, sum增删改的同时，解决区间求和问题低中
线段树(Segment Tree)O(log(n)): insert, find, delete, range max, range min, range
sum, lower, upper; O(1):global max, global min增删改的同时，解决区间求值问题, max, min, sum
等等可以完全替代低中
2.空间复杂度

数据结构堆哈希表前缀树并查集平衡排序二叉树跳跃表树状数组线段树
空间复杂度O(1)O(1)O(1)O(1)O(1)O(1)O(log(n))O(1)

• « 上一篇：模拟银行存款java,模拟银行存取款业务
• » 下一篇：用php写出登录注册,用PHP写一个简单的登录注册页面