广度优先和深度优先的时间复杂度以及空间复杂度(更新)

2021年11月18日 4点热度 0条评论 来源: Better-1

空间复杂度:
算法的空间复杂度并不是计算实际占用的空间,而是计算整个算法的辅助空间单元的个数,与问题的规模没有关系。算法的空间复杂度S(n)定义为该算法所耗费空间的数量级。
S(n)=O(f(n)) 若算法执行时所需要的辅助空间相对于输入数据量n而言是一个常数,则称这个算法的辅助空间为O(1);
递归算法的空间复杂度:递归深度N*每次递归所要的辅助空间, 如果每次递归所需的辅助空间是常数,则递归的空间复杂度是 O(N).=====其实是递归的深度,比如二叉树的深度,同样的空间后面可以继续使用!!!

对于递归算法,由于运行时有附加堆栈,所以递归的空间复杂度是递归的深度*每次压栈所需的空间个数。
递归有运行时堆栈,求的是递归最深的那一次压栈所耗费的空间的个数递归最深的那一次所耗费的空间足以容纳它所有递归过程。(递归是要返回上一层的,所以它所需要的空间不是一直累加起来的)
所以最深的那次压栈就是 递归的空间复杂度

DFS和BFS时间复杂度:O(n)
因为这是树 遍历,我们必须触摸每个节点,使这个O(n),其中n是树中的节点数。

BFS空间复杂度:O(n)
BFS必须至少存储队列中整个树的级别(样本 队列实施)。使用完美的完全平衡二叉树,这将是(n / 2 + 1)个节点(最后一个级别)。 最佳案例 (在此上下文中),树严重不平衡,每层只包含1个元素,空间复杂度为O(1)。 最坏的情况下 将存储(n-1)个节点与一个相当无用的N-ary树,其中除根节点之外的所有节点都位于第二级。

DFS空间复杂度:O(d)
无论实现(递归还是迭代),堆栈(隐式或显式)都将包含d个节点,其中d是树的最大深度。使用平衡树,这将是(log n)节点。 最坏的情况下 对于DFS来说,这将是BFS的最佳案例 最佳案例 DFS将是BFS最糟糕的情况。

    原文作者:Better-1
    原文地址: https://blog.csdn.net/caihuanqia/article/details/111740236
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系管理员进行删除。