哪些网站在哪找的,广告设计需要什么软件,河南网站建设的详细策划,推广整合营销如果不考虑时间和空间的因素#xff0c;所有的问题都可以通过穷举法解决。这也是一开始做AI的强调算力的原因。一#xff0c;概念空间复杂度是指算法在执行过程中所需要的存储空间。包括算法运行时使用的变量/数组/链表 等数据结构所占用的内存空间。通俗一点说#xff0c;就…如果不考虑时间和空间的因素所有的问题都可以通过穷举法解决。这也是一开始做AI的强调算力的原因。一概念空间复杂度是指算法在执行过程中所需要的存储空间。包括算法运行时使用的变量/数组/链表 等数据结构所占用的内存空间。通俗一点说就是一个算法内存用了多少空间复杂度执行了多长时间时间复杂度所以其实程序设计很简单空间复杂度尽量低时间复杂度尽量低。当然了在没有bug的前提下。以前的程序员很在意这两个指标是因为以前的计算机或者芯片存储有限cpu性能弱现在的计算机存储大大的性能过剩所以这两个指标弱一点也没关系。除非一些特殊的需求例如某些ADC采集要在尽量小的时间内将采样数据计算完毕。二常见数据结构的空间复杂度下面是常见数据结构和算法操作的时间复杂度与空间复杂度对照表一、常见数据结构操作复杂度数据结构操作平均时间复杂度最坏时间复杂度空间复杂度数组访问O(1)O(1)O(n)搜索O(n)O(n)插入O(n)O(n)删除O(n)O(n)链表访问O(n)O(n)O(n)搜索O(n)O(n)插入首尾O(1)O(1)删除首尾O(1)O(1)栈入栈O(1)O(1)O(n)出栈O(1)O(1)访问栈顶O(1)O(1)队列入队O(1)O(1)O(n)出队O(1)O(1)访问队首O(1)O(1)哈希表访问O(1)O(n)O(n)搜索O(1)O(n)插入O(1)O(n)删除O(1)O(n)二叉搜索树访问O(log n)O(n)O(n)搜索O(log n)O(n)插入O(log n)O(n)删除O(log n)O(n)平衡二叉树(如 AVL, 红黑树)访问O(log n)O(log n)O(n)搜索O(log n)O(log n)插入O(log n)O(log n)删除O(log n)O(log n)图邻接表访问顶点O(1)O(1)O(nm)访问边O(1)O(1)遍历BFS/DFSO(nm)O(nm)二、常见排序算法复杂度排序算法平均时间复杂度最好时间复杂度最坏时间复杂度空间复杂度稳定性冒泡排序O(n²)O(n)O(n²)O(1)稳定插入排序O(n²)O(n)O(n²)O(1)稳定选择排序O(n²)O(n²)O(n²)O(1)不稳定归并排序O(n log n)O(n log n)O(n log n)O(n)稳定快速排序O(n log n)O(n log n)O(n²)O(log n)不稳定堆排序O(n log n)O(n log n)O(n log n)O(1)不稳定计数排序O(n k)O(n k)O(n k)O(k)稳定桶排序O(n k)O(n)O(n²)O(n k)稳定基数排序O(d * (n k))O(d * (n k))O(d * (n k))O(n k)稳定注n 为数据规模k 为桶/基数的范围d 为基数排序的位数。空间复杂度 O(1) 表示原地排序不占用额外辅助空间。顺序表O (n)其中 n 是顺序表的长度。链表O (n)其中 n 是链表的长度。栈O (n)其中 n 是栈的最大深度。队列O (n)其中 n 是队列的最大长度。哈希表O (n)其中 n 是哈希表中元素的数量。树O (n)其中 n 是树的结点数量。图O (nm)其中 n 是图中顶点的数量m 是图中边的数量。三、常见图算法复杂度算法时间复杂度空间复杂度适用场景深度优先搜索 (DFS)O(n m)O(n)连通性、拓扑排序、强连通分量广度优先搜索 (BFS)O(n m)O(n)最短路径无权图、连通性Dijkstra 算法O((n m) log n)O(n)单源最短路径非负权图Bellman-Ford 算法O(nm)O(n)单源最短路径可处理负权Floyd-Warshall 算法O(n³)O(n²)所有顶点对最短路径Kruskal 算法O(m log m)O(m)最小生成树稀疏图Prim 算法O((n m) log n)O(n)最小生成树稠密图三空间换时间通常使用额外空间的目的就是为了换取时间上的效率也就是我们常说的空间换时间。最经典的空间换时间就是动态规划例如求一个斐波那契数列的第 n 项的值如果不做任何优化就是利用循环进行计算时间复杂度 O (n)但是如果引入了数组将计算结果预先存储在数组中那么每次询问只需要 O (1) 的时间复杂度就可以得到第 n 项的值而这时由于引入了数组所以空间复杂度就变成了 O (n)。空间换时间 vs 时间换空间 典型场景对照表策略核心思想典型场景时间复杂度变化空间复杂度变化适用场景空间换时间用额外的存储空间来减少计算或查询的时间开销1.动态规划斐波那契数列、背包问题用数组存储子问题解避免重复计算。2.缓存/记忆化浏览器缓存、Redis缓存将频繁访问的数据存在内存中。3.哈希表用数组链表实现哈希表将查找时间从O(n)降到O(1)。4.预处理前缀和数组将区间和查询从O(n)降到O(1)。5.位图用位运算存储布尔值快速判断元素是否存在。通常降低如从O(n)→O(1)或O(log n)通常升高如从O(1)→O(n)对响应时间敏感、内存资源相对充足的场景如Web服务、数据库索引、高频查询系统。时间换空间用更多的计算时间来减少对存储空间的占用1.原地排序快速排序、堆排序在原数组上排序空间复杂度O(1)。2.迭代代替递归用循环实现斐波那契数列避免递归栈的O(n)空间开销。3.流式处理逐行读取大文件不将整个文件加载到内存。4.压缩算法用CPU时间对数据进行压缩减少存储占用。5.延迟计算需要时才计算结果不预先存储所有可能值。通常升高如从O(1)→O(n)通常降低如从O(n)→O(1)内存资源受限、对时间要求不苛刻的场景如嵌入式设备、移动应用、处理超大规模数据集。补充说明空间换时间的本质是“预计算存储”通过牺牲内存来换取更快的响应速度。时间换空间的本质是“按需计算复用”通过牺牲CPU时间来节省内存。实际工程中需要根据具体的性能瓶颈和资源约束来选择策略而不是绝对地偏向某一种。