为什么深度优先搜索的空间复杂度不是O(n)？

深度优先搜索（DFS）是一种用于图遍历的算法，它通过递归的方式沿着图的深度方向进行搜索。DFS的空间复杂度不是O(n)，而是O(h)，其中h表示图的最大深度或者树的最大高度。

深度优先搜索的空间复杂度不是O(n)的原因是因为它使用了递归的方式进行搜索，每次递归调用都会在函数调用栈中占用一定的空间。当图或树的深度很大时，函数调用栈的空间占用也会相应增加。

具体来说，DFS在搜索过程中会递归地访问每个节点，并将其标记为已访问。对于每个节点，DFS会递归地访问其相邻节点，直到找到目标节点或者无法继续搜索为止。在递归调用过程中，当前节点的信息会被保存在函数调用栈中，以便在递归返回时能够继续搜索其他节点。

由于DFS是一种深度优先的搜索方式，它会优先访问图或树的深度方向上的节点。因此，当图或树的深度很大时，DFS的空间复杂度也会相应增加。而不同于广度优先搜索（BFS）会使用队列来保存待访问的节点，DFS的空间复杂度主要取决于递归调用栈的深度。

总结起来，深度优先搜索的空间复杂度不是O(n)，而是O(h)，其中h表示图的最大深度或者树的最大高度。在实际应用中，我们需要根据问题的特点和数据规模来选择合适的搜索算法，以满足空间和时间的要求。

腾讯云相关产品和产品介绍链接地址：

腾讯云图数据库 TGraph：https://cloud.tencent.com/product/tgraph
腾讯云云服务器 CVM：https://cloud.tencent.com/product/cvm
腾讯云云原生容器服务 TKE：https://cloud.tencent.com/product/tke
腾讯云人工智能 AI Lab：https://cloud.tencent.com/product/ailab
腾讯云物联网平台 IoT Hub：https://cloud.tencent.com/product/iothub
腾讯云移动开发平台 MSDK：https://cloud.tencent.com/product/msdk
腾讯云对象存储 COS：https://cloud.tencent.com/product/cos
腾讯云区块链服务 TBC：https://cloud.tencent.com/product/tbc
腾讯云元宇宙服务 TUS：https://cloud.tencent.com/product/tus

相关·内容

一个时间复杂度O(n)，空间复杂度为O(1)的排序算法

由于固定长度的hash数组，所以空间复杂度与待排序数组数据规模n没有关系，也就是说空间复杂度为O(1)。...hash[MAXN]; template void Sort(T arr[],int n){ fill(hash,hash+MAXN,false); //时间复杂度为O(...n) for(int i=0;i<n;++i){ hash[arr[i]] = true;//标记arr[i]出现过 } //时间复杂度为O(MAXN) int k=0; for(int...i=0;i<MAXN;++i){ if(hash[i] == true){ arr[k++] = i; } } 总的时间复杂度为O(n+MAXN),即O(n) } void show...2.对于一个几乎有序的待排序数组数组，其时间复杂任然为O(n)。

1.1K1 0

【漫画】为什么说O(n)复杂度的基数排序没有快速排序快？

这样的话，不是可以排的更快吗？ ? 老大：脑子反应的挺快啊。是的，是可以以最高位来排序的，而且也像你说的，以最高位来排序的话，是可以减少数据之间比较的次数。...这样子的话，空间花费不仅大，而且看起来有点背离基数排序最初的思想了（“背离”这个词，个人感觉而已）。所以，我们一般采用从最低位到最高位的顺序哦。 ? 关于基数排序，还有以下几个问题，你不妨也想一想?...1、基数排序是一种用空间换时间的排序算法，数据量越大，额外的空间就越大? 我的想法：我觉得基数排序并非是一种时间换空间的排序，也就是说，数据量越大，额外的空间并非就越大。...因为在把元素放进桶的时候，是完全可以用指针指向这个元素的，也就是说，只有初始的那些桶才算是额外的空间。 2、居然额外空间不是限制基数排序速度的原因，那为啥基数排序没有快速排序快呢？...基数的时间复杂度为O(n)，不过他是忽略了常数项，即实际排序时间为kn(其中k是常数项)，然而在实际排序的过程中，这个常数项k其实是很大的，这会很大程度影响实际的排序时间，而像快速排序虽然是nlogn，

7201 0

请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法，判断其是否为回文结构

对于一个链表，请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法，判断其是否为回文结构。给定一个链表的头指针A，请返回一个bool值，代表其是否为回文结构。保证链表长度小于等于900。

5281 0

二叉树的所有路径

当然，深度优先搜索也可以使用非递归的方式实现，这里不再整述。 复杂度分析 ·时间复杂度:o(N²)，其中N表示节点数目。...在深度优先搜索中每个节点会被访问一次且只会被访问一次，每一次会对path变量进行拷贝构造，时间代价为O(N)，故时间复杂度为O(N²)。空间复杂度:o(N²)，其中N表示节点数目。...最好情况下，当二叉树为平衡二叉树时，它的高度为log N，此时空间复杂度为O((log N)²)。方法二:广度优先搜索我们也可以用广度优先搜索来实现。...如果它不是叶子节点，则将它的所有孩子节点加入到队列的末尾。当队列为空时广度优先搜索结束，我们即能得到答案。 复杂度分析 ·时间复杂度:o(N²)，其中N表示节点数目。分析同方法一。...·空间复杂度:o(N²)，其中N表示节点数目。在最坏情况下，队列中会存在N个节点，保存字符串的队列中每个节点的最大长度为N，故空间复杂度为o(N²)。

2983 0

课程表

这其实就是对图进行深度优先搜索的时间复杂度。空间复杂度: O(n + m)。...题目中是以列表形式给出的先修课程关系，为了对图进行深度优先搜索，我们需要存储成邻接表的形式，空间复杂度为 O(n + m)。...在深度优先搜索的过程中，我们需要最多 O(n) 的栈空间（递归）进行深度优先搜索，因此总空间复杂度为 O(n + m)。广度优先搜索拓扑排序也可以使用广度优先搜索实现。...这其实就是对图进行广度优先搜索的时间复杂度。空间复杂度: O(n + m)。...在广度优先搜索的过程中，我们需要最多 O(n) 的队列空间（迭代）进行广度优先搜索。因此总空间复杂度为 O(n + m)。

7721 0

【灵魂 |数据结构与算法】数据结构必备经法（开山篇），一起修炼算法经法！

只关注循环最多的一段代码加法原则：取量级最大的复杂度 乘法原则：取量级结果最大的分为两类，多项式量级和非多项式量级。其中，非多项式量级只有两个：O(2^n) 和 O(n!)。...类比一下，空间复杂度全称就是渐进空间复杂度（asymptotic spacecomplexity），表示算法的存储空间与数据规模之间的增长关系。...查看循环最多的变量生成的一段代码常见的复杂度并不多，从低阶到高阶有：O(1)、O(logn)、O(n)、O(nlogn)、O(n )。...哈希函数的设计和冲突解决方法哈希表在查找和去重等问题中的应用树与图：二叉树的遍历（前序、中序、后序）二叉搜索树的性质和操作堆和优先队列的基本概念和应用图的表示方法和遍历算法（深度优先搜索...、广度优先搜索）排序和搜索：常见排序算法（冒泡排序、插入排序、快速排序等）高级排序算法（归并排序、堆排序等）二分查找和其他搜索算法的实现和应用动态规划：动态规划的基本概念和解题思路

1661 0

二叉树的最小深度

对于每一个非叶子节点，我们只需要分别计算其左右子树的最小叶子节点深度。这样就将一个大问题转化为了小问题，可以递归地解决该问题。 复杂度分析时间复杂度:O(N)，其中N是树的节点数。...·空间复杂度:O(H)，其中H是树的高度。空间复杂度主要取决于递归时栈空间的开销，最坏情况下，树呈现链状，空间复杂度为O(N)。...平均情况下树的高度与节点数的对数正相关，空间复杂度为O(log N)。方法二:广度优先搜索同样，我们可以想到使用广度优先搜索的方法，遍历整棵树。...当我们找到一个叶子节点时，直接返回这个叶子节点的深度。广度优先搜索的性质保证了最先搜索到的叶子节点的深度—定最小。 复杂度分析时间复杂度:O(N)，其中N是树的节点数。对每个节点访问一次。...·空间复杂度:O(N)，其中N是树的节点数。空间复杂度主要取决于队列的开销，队列中的元素个数不会超过树的节点数。

2832 0

LintCode 数字三角形题目分析1 （常规的动态规划解法）分析2 （如果你只用额外空间复杂度O(n)的条件）

题目给定一个数字三角形，找到从顶部到底部的最小路径和。每一步可以移动到下面一行的相邻数字上。...** 注意事项如果你只用额外空间复杂度O(n)的条件下完成可以获得加分，其中n是数字三角形的总行数。** 样例比如，给出下列数字三角形： ?...public int minimumTotal(int[][] triangle) { // write your code here //从底往上，把每一行的元素改为其下一行能与之相加的两个数得到的和的最小值...min) min = dp[row-1][i]; } return min; } 分析2 （如果你只用额外空间复杂度...O(n)的条件）从顶部到底部的最小路径和等于从底部到顶部的最小路径和 //从倒数第二层开始，从底层到每一层每个数字的最小路径长度等于，从底层到该层的下层相邻数字的最小路径长度中的较小值，加上该层该数字的值

6692 0

Leetcode No.257 二叉树的所有路径

最直观的方法是使用深度优先搜索。...在深度优先搜索遍历二叉树时，我们需要考虑当前的节点以及它的孩子节点。如果当前节点不是叶子节点，则在当前的路径末尾添加该节点，并继续递归遍历该节点的每一个孩子节点。...时间复杂度：O(N^2)，其中 N 表示节点数目。...在深度优先搜索中每个节点会被访问一次且只会被访问一次，每一次会对 path 变量进行拷贝构造，时间代价为 O(N)，故时间复杂度为 O(N^2) 空间复杂度：O(N^2)，其中 N表示节点数目。...) = O(N^2)，空间复杂度为 O(N^2)。最好情况下，当二叉树为平衡二叉树时，它的高度为logN，此时空间复杂度为 O((logN)^2)。

1.3K2 0

二叉树的最小深度

原题样例：二叉树的最小深度 ????C#方法：深度优先搜索 ????Java 方法一：深度优先搜索 ????Java 方法二：广度优先搜索 ????总结 ????往期优质文章分享 ????...C#方法：深度优先搜索既然是求解二叉树的最小深度，那我们就把二叉树整个遍历一遍然后判断深度就好了使用深度优先搜索的方法，遍历整棵树，记录最小深度。...内存消耗：50 MB，在所有 C# 提交中击败了50.00%的用户 复杂度分析时间复杂度：O( n ),其中 n 是树的节点数空间复杂度：O( H )，其中 H 是树的高度 ????...内存消耗：59 MB，在所有 Java 提交中击败了16.41%的用户 复杂度分析时间复杂度：O( n ),其中 n 是树的节点数空间复杂度：O( H )，其中 H 是树的高度 ????...内存消耗：58 MB，在所有 Java 提交中击败了58.59%的用户 复杂度分析时间复杂度：O(n)其中 n 是树的节点数空间复杂度：O(n)其中 n 是树的节点数 ????

2592 0

【小Y学算法】⚡️每日LeetCode打卡⚡️——28.二叉树的最大深度

因此我们可以用「深度优先搜索」的方法来计算二叉树的最大深度。具体而言，在计算当前二叉树的最大深度时，可以先递归计算出其左子树和右子树的最大深度，然后在 O(1) 时间内计算出当前二叉树的最大深度。...内存消耗：25.7 MB，在所有 C# 提交中击败了10.73%的用户 复杂度分析时间复杂度：O(n) 空间复杂度：O(n) ---- ????...因此我们可以用「深度优先搜索」的方法来计算二叉树的最大深度。具体而言，在计算当前二叉树的最大深度时，可以先递归计算出其左子树和右子树的最大深度，然后在 O(1) 时间内计算出当前二叉树的最大深度。...空间复杂度：O( height ) 其中height 表示二叉树的高度。递归函数需要栈空间，而栈空间取决于递归的深度，因此空间复杂度等价于二叉树的高度。 ????...与方法一同样的分析，每个节点只会被访问一次。空间复杂度：O(n),此方法空间的消耗取决于队列存储的元素数量，其在最坏情况下会达到 O(n)。 ---- ????

2274 0

二叉树的最大深度

因此我们可以用「深度优先搜索」的方法来计算二叉树的最大深度。具体而言，在计算当前二叉树的最大深度时，可以先递归计算出其左子树和右子树的最大深度，然后在O(1)时间内计算出当前二叉树的最大深度。...复杂度分析时间复杂度:O(n)，其中n为二叉树节点的个数。每个节点在递归中只被遍历一次。空间复杂度:O(height)，其中height表示二叉树的高度。...递归函数需要栈空间，而栈空间取决于递归的深度，因此空间复杂度等价于二叉树的高度。...方法二:广度优先搜索我们也可以用「广度优先搜索」的方法来解决这道题目，但我们需要对其进行—些修改，此时我们广度优先搜索的队列里存放的是「当前层的所有节点」。...复杂度分析 ·时间复杂度:O(n)，其中n为二叉树的节点个数。与方法一同样的分析，每个节点只会被访问一次。 ·空间复杂度:此方法空间的消耗取决于队列存储的元素数量，其在最坏情况下会达到O(n)。

2472 0

【地铁上的面试题】--基础部分--数据结构与算法--排序和搜索算法

在平均情况下，顺序搜索需要遍历数据集的一半，因此时间复杂度为O(n/2)，可以简化为O(n)。顺序搜索的空间复杂度是O(1)，即常数级别的额外空间。...平均情况下为O(log n)，在平均情况下，二分搜索的时间复杂度也是O(log n)。二分搜索的空间复杂度是O(1)，它不需要额外的空间来存储数据结构或中间结果。...平均情况下的时间复杂度也是O(V+E)，因为深度优先搜索访问每个节点的概率相对均匀。在最好情况下如果使用递归实现深度优先搜索，并且树的深度很小，那么递归调用的空间复杂度将是O(1)。...在最坏情况下如果树的深度非常大，递归调用的层数可能达到树的最大深度，此时空间复杂度为O(D)，其中D是树的深度。平均情况下的空间复杂度也是O(D)，取决于树的平均深度。...Tip：如果使用了辅助栈来实现深度优先搜索，那么空间复杂度将取决于栈的大小，即O(D)。在实际应用中，为了避免栈溢出，可以通过迭代方式或限制递归深度来进行优化。

2201 0

☆打卡算法☆LeetCode 111、二叉树的最小深度算法解析

最小深度是从根节点到最近叶子节点的最短路径上的节点数量。说明：叶子节点是指没有子节点的节点。...3,9,20,null,null,15,7] 输出： 2 示例 2：输入： root = [2,null,3,null,4,null,5,null,6] 输出： 5 二、解题 1、思路分析这道题首先想到的就是深度优先搜索的方法...时间复杂度 ： O(N) 其中N是树的节点数，对每个节点只访问一次。...空间复杂度： O(H) 其中H是树的高度，空间复杂度主要取决于递归时的开销，递归的空间复杂度为O(N)，平均情况下树的高度与节点数的对数正相关，空间复杂度为O(log N)，总的时间复杂度就是O(H)。...三、总结这道题用了广度优先搜索方法，同样，也可以使用广度优先搜索的方法去遍历整棵树。对于这道题来书，广度优先搜索方法可以保证最先搜索到的叶子节点的深度一定最小。

1342 0

一文学会「回溯搜索算法」解题技巧

此时可以将空间复杂度降到 O(1)（不包括 path 变量和 res 变量和递归栈空间消耗），本 Python 代码正好展示了这样的写法；（2）哈希表，代码留给读者完成。...；如果每一个状态都去创建新的变量，时间复杂度是 O(N)，并且也有空间的消耗。...搜索问题的状态空间一般很大，在候选数比较多的时候，在非叶子结点上创建新的状态变量的性能消耗就很严重；就本题而言，只需要叶子结点的那个状态，在叶子结点执行拷贝，时间复杂度是 O(N)。...路径变量在深度优先遍历的时候，结点之间的转换只需要 O(1)。 为什么不使用广度优先遍历？...这道题用广度优先遍历写是完全可以的，我尝试过，代码写出来非常不美观。感兴趣的朋友也可以尝试写一下，尝试写广搜的目的是更好地体会为什么“深搜”能成为强大的“回溯搜索算法”，而广搜不是。

1.2K1 0

二叉树的最大深度（LeetCode 104）

4.解题思路方法一：深度优先搜索如果我们知道了左子树和右子树的最大深度 l 和 r，那么该二叉树的最大深度即为 max(l, r) + 1。而左子树和右子树的最大深度又可以以同样的方式进行计算。...因此我们可以用「深度优先搜索」的方法来计算二叉树的最大深度。具体而言，在计算当前二叉树的最大深度时，可以先递归计算出其左子树和右子树的最大深度，然后在 O(1) 时间内计算出当前二叉树的最大深度。...时间复杂度： O(n)，其中 n 为二叉树节点的个数。每个节点在递归中只被遍历一次。空间复杂度： O(height)，其中 height 表示二叉树的高度。...递归函数需要栈空间，而栈空间取决于递归的深度，因此空间复杂度等价于二叉树的高度。...时间复杂度： O(n)，其中 n 为二叉树的节点个数。与方法一同样的分析，每个节点只会被访问一次。空间复杂度：此方法空间的消耗取决于队列存储的元素数量，其在最坏情况下会达到 O(n)。

1541 0

深度优先算法和广度优先算法

广度优先算法的实现广度优先算法是一种分层的查找过程，每向前走一步可能会访问一批顶点，不像深度优先搜索算法那样有回溯的情况，因此它不是一个递归的算法。...O（n）。...采用邻接表存储方式时，每个顶点均需要搜索一次，故时间复杂度O(|V|)，在搜索任意节点的邻接点时，每条边至少访问一次，故时间复杂度为O(E)，算法总时间复杂度为O(E+V)。...深度优先算法深度优先算法的实现图的深度优先算法类似于树的先序遍历，DFS算法是一个递归算法，需要借助一个工作栈，故其空间复杂度度为O(V)。...深度优先算法的邻接矩阵的时间复杂度为O(V*V),邻接表的时间复杂度为O（V+E）。

8596 0

☆打卡算法☆LeetCode 207. 课程表算法解析

那么对于一个有向图，可以分为两种情况：不是有向无环图，也就是不满足任意一条有向边(u,v)，u在排列中都出现在v的前面，那么就不存在满足要求的排列。是有向无环图，但是它的拓扑排序可能不止一种。...求有向图G是否存在拓扑排序，可以判断是否有一种符合要求的课程学习顺序，可以使用深度优先搜索的流程，用一个栈来存储所有已经搜索完成的节点。...那么对整个图进行一次深度优先搜索，对每个节点回溯的时候，将该节点放入栈中，最后从栈顶到栈底的序列就是一种拓扑排序。...时间复杂度：O(n+m) 其中n为课程数，m为先修课程的要求数，时间复杂度主要是对图进行深度优先搜索的时间复杂度。...空间复杂度：O(n+m) 其中n为课程数，m为先修课程的要求数，在深度优先搜索的过程中，需要最多O(n)的栈空间进行深度优先搜索，因此总时间复杂度为O(n+m)。

3692 0

LeetCode算法-树的遍历

;复杂度分析：时间复杂度：O(n)：n为二叉树节点数。空间复杂度：O(n)：n为二叉树节点数。递归调用的栈深度取决于二叉树的高度，二叉树最坏情况下为一条链，此时高度为 N，因此空间复杂度为 O(N)。...空间复杂度：O(n)：最差情况下，空间复杂度为O(n)。二叉树的所有路径思路：本题考虑使用深度优先遍历。如果当前节点有左子树或右子树，就递归调用函数，直到左右子树都不存在，此时就是我们要找的的路径。...在深度优先搜索中每个节点会被访问一次且只会被访问一次，每一次会对 path 变量进行拷贝构造，时间代价为 O(N)，故时间复杂度为 O(N^2)。空间复杂度：O(n^2)：n为二叉树节点数。...空间复杂度：O(n)：n为二叉树节点数。路径总和思路：考虑深度优先遍历记录从根节点到当前节点的和，与target比较。...空间复杂度：O(n)剑指 Offer 37. 序列化二叉树总结继续对树的深度/广度优先遍历，先中后序遍历，层序遍历等遍历和递归的方法，有更深入的理解和学习。

6433 0

Python-图-如何找到三度好友？

这个时候，每个顶点都要进出一遍队列，每个边也都会被访问一次，所以，广度优先搜索的时间复杂度是 O(V+E)，其中，V 表示顶点的个数，E 表示边的个数。...当然，对于一个连通图来说，也就是说一个图中的所有顶点都是连通的，E 肯定要大于等于 V-1，所以，广度优先搜索的时间复杂度也可以简写为 O(E)。...广度优先搜索的空间消耗主要在几个辅助变量 visited 、queue 、prev 上。这三个存储空间的大小都不会超过顶点的个数，所以空间复杂度是 O(V)。...度内的好友有：3,1, 4、图的深度优先遍历只需要将广度优先遍历中队列改为栈，就变成了深度优先遍历算法，请自行思考为什么。...这里仅仅是把队列变成了栈，因此时间复杂度和空间复杂度和广度优先遍历算法是一样的。

7383 0

点击加载更多

扫码

添加站长进交流群

领取专属 10元无门槛券

手把手带您无忧上云

为什么深度优先搜索的空间复杂度不是O(n)？

相关·内容

一个时间复杂度O(n)，空间复杂度为O(1)的排序算法

【漫画】为什么说O(n)复杂度的基数排序没有快速排序快？

请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法，判断其是否为回文结构

二叉树的所有路径

课程表

【灵魂 |数据结构与算法】数据结构必备经法（开山篇），一起修炼算法经法！

二叉树的最小深度

LintCode 数字三角形题目分析1 （常规的动态规划解法）分析2 （如果你只用额外空间复杂度O(n)的条件）

Leetcode No.257 二叉树的所有路径

二叉树的最小深度

【小Y学算法】⚡️每日LeetCode打卡⚡️——28.二叉树的最大深度

二叉树的最大深度

【地铁上的面试题】--基础部分--数据结构与算法--排序和搜索算法

☆打卡算法☆LeetCode 111、二叉树的最小深度算法解析

一文学会「回溯搜索算法」解题技巧

二叉树的最大深度（LeetCode 104）

深度优先算法和广度优先算法

☆打卡算法☆LeetCode 207. 课程表算法解析

LeetCode算法-树的遍历

Python-图-如何找到三度好友？

扫码

相关资讯

热门标签

活动推荐

运营活动

社区

活动

资源

关于

腾讯云开发者

热门产品

热门推荐

更多推荐