您的位置: 首页 > 文章 > 算法与数据结构你需要了解

算法与数据结构你需要了解

分类: 文章 • 2025-01-26 09:23:58

数据结构分类

按照存储结构来分

线性结构：Array、Stack/Queue、PriorityQueue(heap)、LinkedList（single/double)
非线性结构：Tree/Binary Tree、Binary Search Tree、HashTable、DisjointSet并查集、Trie字典树、Bloom Filter、LRU Cache

常见算法

General Coding 经典算法
In-order/Pre-order/Post-order traversal 前中后序遍历
Greedy 贪心算法
Recursion/Backtrace 回溯/递归
Depth -first Search 深度优先遍历
Breadth -first Search 广度优先遍历
Divide and Conqner 分治算法
Dynamic Programming 动态规划
Binary Search 二分查找
Graph 图

时间复杂度

O(1) 常数复杂度
O(logn) 对数复杂度
O(n) 线性时间复杂度
O(n^2) 平方
O(n^3) 立方
O(2^n) 指数
O(n!) 阶乘

O(1) < O(n) < O(nlogn) < O(n^2) < O(2^n) < O(n!)

数据量越大，时间复杂度低的，用的时间越少

/**
 * 1+2+3+...+n
 */
 
 y = 0
 for i = 1 to n:
 	y = i + y
 	
时间复杂度为O(n) ,然后对其进行优化使用公式

y = n * (n + 1) / 2 

时间复杂度为O(1)

斐波那契数列 1 1 2 3 5 8 13 21...n
F(n) = F(n-1) + F(n-2)

def fib(n):
	if (n==0 or n==1)
		return 1
	return fib(n-1) + fib(n-2)
这个的时间复杂度为O(2^n)
对于递归的算法 我们可以 主定理公式 来求解

常见数据结构：
算法与数据结构你需要了解
数据结构和算法学习图：