精华内容
下载资源
问答
  • 先用DFS计算时间复杂度和空间复杂度 时间复杂度(算法对大小为n-T的实例执行基本操作的次数(n)): 考虑最坏情况,也就是说我们找了整张中国地图的区县最后才找到山东菏泽曹县。时间复杂度就是找每个节点这个过程的...

    现在我们设定任务为到山东菏泽曹县买牛逼,需要利用深度优先算法(DFS)和广度优先算法(BFS)在中国、省会、市、区县这张大的树中搜索到曹县,那么这个任务Goal就是找到曹县。
    搜索图
    假如图的最大路径长度m和最大分支因子b

    先用DFS计算时间复杂度和空间复杂度
    DFS

    时间复杂度(算法对大小为n-T的实例执行基本操作的次数(n)):
    考虑最坏情况,也就是说我们找了整张中国地图的区县最后才找到山东菏泽曹县。时间复杂度就是找每个节点这个过程的数量,总共找了的次数,就是图中弧的个数。
    按最坏情况每个节点的最大分支因子都是b,从中国到各个省(中国->河南、中国->北京、中国->上海、中国->山东、…)总共由b个弧;从各个省份到市(河南->周口、河南->郑州、山东->济南、山东->菏泽…)总共有b^2个弧;从各个市到各个县区(…)有b ^3个弧;…
    按图的最大路径长度m,也就是弧的总数为b+b^2+b ^3 + b ^4 + …+b ^m 数量级是b ^m
    因此用DFS计算时间复杂度是O(b^m)。
    空间复杂度(算法用于执行和产生结果的输入值(包括算法)的内存量。):
    看看最坏情况下搜索过程中堆栈里面有什么
    栈里最多有多少东西
    所以通过上面这张图可以看出栈里最最坏情况下有mb+1-m个,数量级是mb,所以空间复杂度是O(bm)

    写不下去了,快考试了,先放这,以后有空继续写。

    继续写
    用BFS计算时间复杂度和空间复杂度
    BFS
    BFS的时间复杂度,考虑最坏情况,仍然是遍历整张地图才找到曹县,所以时间复杂度依照仍然是弧的总数量,按图的最大路径长度m,也就是弧的总数为b+b^2+b ^3 + b ^4 + …+b ^m 数量级是b ^m
    空间复杂度,BFS的搜索过程相当于一个队列,所以我们只要找到这个队列在最坏情况下的最大占用内存数量级,就找到了它的空间复杂度。
    所以找曹县的过程中队列中发生的变化大致是
    中国
    河南、上海、北京…… 山东
    周口、郑州…………济南、菏泽
    川汇区、淮阳区………市中区、历下区……曹县
    所以最大内存的数量级应该是跟各个区县的数量级相同,也就是 b ^m

    展开全文
  • DFS算法是一一个递归算法,需要借助一个递归工作栈,故它的空间复杂度为O(N)。遍历图的过程实质上是对每个顶点查找其邻接点的过程,其耗费的时间取决于所采用结构。 邻接表表示时,查找所有顶点的邻接点所需时间为...

    1.DFS时间复杂度

    • DFS算法是一一个递归算法,需要借助一个递归工作栈,故它的空间复杂度为O(N)。遍历图的过程实质上是对每个顶点查找其邻接点的过程,其耗费的时间取决于所采用结构。

    • 邻接表表示时,查找所有顶点的邻接点所需时间为O(E),访问顶点的邻接点所花时间为O(N),此时,总的时间复杂度为O(N+E)。

    • 邻接矩阵表示时,查找每个顶点的邻接点所需时间为O(N),要查找整个矩阵,故总的时间度为O(N^2)。

    2.BFS时间复杂度

    • BFS是一种借助队列来存储的过程,分层查找,优先考虑距离出发点近的点。无论是在邻接表还是邻接矩阵中存储,都需要借助一个辅助队列,N个顶点均需入队,最坏的情况下,空间复杂度为O(N)。

    • 邻接表形式存储时,每个顶点均需搜索一次,时间复杂度T1=O(N),从一个顶点开始搜索时,开始搜索,访问未被访问过的节点。最坏的情况下,每个顶点至少访问一次,每条边至少访问1次,这是因为在搜索的过程中,若某结点向下搜索时,其子结点都访问过了,这时候就会回退,故时间复 杂度为O(E),算法总的时间复 度为O(N+E)。

    • 邻接矩阵存储方式时,查找每个顶点的邻接点所需时间为O(N),即该节点所在的该行该列。又有n个顶点,故算总的时间复杂O(N^2)。

    3. 若将n个顶点e条弧的有向图采用邻接表存储,则拓扑排序算法的时间复杂度为O(n+e)

    4.G是一个非连通无向图,共有22条边,则该图至少有(9)个顶点。

    全连通图的定点 n 和边数 m 满足:m = n(n-1)/2,那么边 m = 22 时,
    图 G: n(n-1)/2 >= 22
    解得:n >= 8
    而且,当 n = 7 时,全连通图 G’ 的边数 m = 21
    当我们把第 8 个定点专加上来,必然还要再在这个定点和上面7个定点相连,以属便构成第 22 边(8个顶点不足以构成22边非连通图)
    加上第 9 个定点后,可以在 (8, 9) 之间构成第22边,或者,选择 8, 或 9 作为孤立点,构成非连通图
    至少有 9 个顶点

    5.下列AOE 网表示一项包含 8 个活动的工程。通过同时加快若干活动的进度可以缩短整个工程的工期。下列选项中,加快其进度就可以缩短工程工期的是(C )。

    • A c 和 e
    • B d 和 e
    • C f 和 d
    • D f 和 h

    详解来自牛客:这个网有三条关键路径:
    b、d、c、g
    b、d、e、h
    b、f、h
    缩短工期的活动要涵盖三条路径。

    展开全文
  • DFS和BFS时间复杂度:O(n) 因为这是树 遍历,我们必须触摸每个节点,使这个O(n),其中n是树中的节点数。 BFS空间复杂度:O(n) BFS必须至少存储队列中整个树的级别(样本 队列实施)。使用完美的完全平衡二叉树...

    空间复杂度:
    算法的空间复杂度并不是计算实际占用的空间,而是计算整个算法的辅助空间单元的个数,与问题的规模没有关系。算法的空间复杂度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最糟糕的情况。

    展开全文
  • bfs和dfs都是遍历图的方法。 说明: bfs只能做权重为1或者相同的 “最短路” 空间dfs 复杂度为最大深度 h。这也是stack最大容量。 bfs 复杂度为 2^h。因为满二叉树 最下面一层为 2^(h-1)个节点。 这是个queue...

    深度优先搜索和宽度优先搜索

    bfs和dfs都是遍历图的方法。

    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-oPE5oqDt-1591066356009)(../../图库/1590211529631.png)]

    说明

    • bfs只能做权重为1或者相同的 “最短路”
    • 空间上
      • dfs 复杂度为最大深度 h。这也是stack最大容量。
      • bfs 复杂度为 2^h。因为满二叉树 最下面一层为 2^(h-1)个节点。 这是个queue最大容量。

    bfs——广度优先算法(暴搜)

    • 适合解决最小步数问题。(bfs只能做权重为1或者相同的 “最短路”)
    • 比dfs用时间更短
    • dfs是穷举。到一个点需要3步,那么bfs会在第三层就找到。

    算法思路

    • 一层层搜索

    • 将一个点所有邻居加入队列中。

    • 然后将列队中一个点,所有邻居加入队列。重复这个过程。

    • 需要判重。加入过的。不再加入了。

    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-gG6ClO1O-1591066356013)(../../图库/1590211235849.png)]

    模板

    queue<int> q;
    st[1] = true; // 表示1号点已经被遍历过
    q.push(1);
    
    while (q.size())
    {
        int t = q.front();
        q.pop();
    
        for (int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];
            if (!st[j])
            {
                st[j] = true; // 表示点j已经被遍历过
                q.push(j);
            }
        }
    }
    

    例题

    迷宫

    从左上到右下角。最少的步数。

    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-qZ7hcSQx-1591066356017)(../../图库/1590211035398.png)]

    想法

    • bfs + 记忆化

    • d[i][j]代表(00)到(i,j)最短距离
      
    • bfs第一次搜索到的右下角的点。d数组的值就是答案。

    // AcWing 844. 走迷宫
    // Created by majoe on 2020/5/20.
    //https://www.acwing.com/activity/content/problem/content/907/1/
    
    #include <bits/stdc++.h>
    using namespace std;
    const int N = 110;
    int n ,m;
    int mi[N][N],d[N][N];
    int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
    
    int bfs(){
        queue<int> h;
        queue<int> l;
        //h代表行,l代表列。
        h.push(1);
        l.push(1);
    
        memset(d,-1, sizeof(d));
        d[1][1] = 0; // (1,1)到(1,1)距离为0
        //不为空
        while (!h.empty()){
            int a = h.front(), b = l.front();
            h.pop(); l.pop();
            for (int i = 0; i < 4; ++i) {
                int xx = a + dx[i];
                int yy = b +dy[i];
                if(xx>=1 && yy >=1 &&  xx <= n && yy <= m  && mi[xx][yy] == 0 && d[xx][yy] == -1){
                    //d[xx][yy] = 1表示xx,yy没被访问过
                    h.push(xx);l.push(yy);
                    d[xx][yy] = d[a][b]+1;
                }
            }
        }
        return d[n][m];
    }
    
    int main(){
        cin >> n >> m;
        for (int i = 1; i <= n ; ++i) {
            for (int j = 1; j <= m; ++j) {
                cin >> mi[i][j];
            }
        }
        int ans = bfs();
        cout << ans;
        return 0;
    }
    

    深度优先搜索 - dfs

    特点

    • 每次搜索都会到头
    • 一般dfs遍历图。用邻接表比较好。时间复杂度低.
    • 并且如果没有路的话,会回溯。也就是“回头”。
    • 利用stack。进行回溯
      • 回溯需要恢复现场
    • 同时需要有一个vis数组,将用过的点。记录下

    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-RHuUnzJr-1591066356023)(../../图库/1590211824694.png)]

    算法思路

       void dfs(int step){//变量据题而命
        if(判断边界){
            ...
        }
        //尝试每种可能;
        for(int i=1;i<=n;i++){
            //保证没有被访问过
            if(vis[step]){
             vis[step] = true;
            dfs(step+1);//继续下一步
            vis[step] = false; // 回溯
            }
        }
        return;
    }
    

    一般dfs遍历图。用邻接表比较好。时间复杂度低.

    模板

    int dfs(int u)
    {
        st[u] = true; // st[u] 表示点u已经被遍历过
    
        for (int i = h[u]; i != -1; i = ne[i])
        {
            int j = e[i];
            if (!st[j]) dfs(j);
        }
    }
    

    例题

    数字的全排列

    1-n数字的全排列。n=3时。

    #include <iostream>
    using namespace std;
    const int N = 10;
    
    int path[N];
    bool st[N];
    int n;
    
    // 计算u->n的所经过的路径path
    void dfs(int u) 
    {
        // 边界条件
        if (u == n) 
        {
            for (int i = 0; i < n; i++) printf("%d ", path[i]);
            puts("");
            return;
        }
        else 
        {
            for (int i = 1; i <= n; i++) 
            {
                if (!st[i]) 
                {
                    path[u] = i;
                    st[i] = true;
                    dfs(u+1); // 回溯之后, 
                     
                    st[i] = false;
                }
            }
        }
    }
    
    int main()
    {
        scanf("%d", &n);
        dfs(0);
        return 0;
    }
    

    树的重心

    题意

    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-D9WFALvq-1591066356037)(../../图库/1590233175578.png)]

    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-uxkgVN53-1591066356038)(../../图库/1590233157386.png)]

    想法

    • dfs
    • 利用dfs遍历每一个节点。dfs()返回该节点下包含多少个节点。记做sum
    • 当然,dfs(u)时,会切分子节点为若干个子树。记录子树的包含的最大节点数为 res
    • 那么 max(res,n - sum) 的最小值就是 答案。

    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-f8wefJcX-1591066356041)(../../图库/1590236944675.png)]

    实现

    //
    //
    #include <bits/stdc++.h>
    using namespace std;
    
    const int N = 2e5 +10; //无向图,容量应该是两倍
    int n;//n个节点
    int h[N],ne[N],e[N],idx;
    int ans = 1e9;
    int vis[N];
    
    void add(int a, int b){
        e[idx] = b; ne[idx] = h[a];h[a] = idx++;
    }
    
    //得到以U为顶点,包含的点的个数
    int dfs(int u){
        vis[u] = 1;//本次点只能遍历一次。所以不用回溯
    
        int sum = 1,res=0;// res表示u节点某一节点包含节点的个数
        //遍历u的直接边
        for (int i = h[u]; i != -1 ; i = ne[i]) {
            int j = e[i];//j为u指向的点
            if (vis[j]) continue;
            int s = dfs(j);
            res = max(res,s);
            sum += s; // sum表示 u 的包含的总结点树
        }
        res = max(res,n-sum);
        ans = min(ans,res);
        return sum;
    }
    
    
    int main(){
    
        cin >> n;
        memset(h,-1 , sizeof(h));
        for (int i = 0; i < n - 1; ++i) {
            //n-1条边
            int a,b;
            cin >> a >> b;
            add(a,b);
            add(b,a);//无向图
        }
        dfs(1);//遍历第一个点
        cout << ans << endl;
        return 0;
    }
    
    展开全文
  • 空间复杂度

    2021-04-18 09:11:56
    DFS和BFS时间复杂度:O(n) 因为这是树 遍历,我们必须触摸每个节点,使这个O(n),其中n是树中的节点数。 BFS空间复杂度:O(n) BFS必须至少存储队列中整个树的级别(样本 队列实施)。使用完美的完全平衡二叉树...
  • DFSBFS

    2019-09-03 11:32:23
    搜索算法是有目的性的穷举问题的部分或所有可能情况,从而求出可行解的方法。...其中的剪枝就是根据题意减去没必要遍历的状态,从而减少时间和空间复杂度。 这里提一下一个极其强大的剪枝方法: 奇偶性剪枝;博...
  • DFS:不撞南墙不回头,所以相对于BFS 找到的不一定是最优解,但是其对于空间的消耗较少,因为不需要存储临时节点   对于DFS,其实现方法类似于先序遍历,不断递归的调用DFS函数,依次向下搜寻。   首先是图结构体...
  • 文章目录0. 前言1. 输入数据分析2. 递归问题及主定理3. 双指针4. 单调栈单调队列5.... 空间复杂度分析 转自大佬博客总结 0. 前言 养成计算时间复杂度的习惯。 养成做 lc 尽量从算法角度去考虑,而不是暴力
  • 目录 1. 树的BFS和图的BFS的区别 2. DFS的回溯 3. BFS复杂度分析 4. DFS复杂度分析 1. 树的BFS和图的BFS的区别 ...所以,对于图来说,如果不判重,时间和空间都将产生极大的浪费。 2. DFS...
  • 搜索:DFSBFS

    2018-09-04 16:33:48
    基本概念 状态:对问题在某一时刻的进展情况的数学描述 状态转移:从一个状态扩展出其他状态的过程 搜索树:由若干状态状态转移形成的树形结构 ...空间复杂度:O(n*m) 伪代码框架 void...
  • 最短路径问题总结 ...最短路径算法(一)–DFS/BFS求解(JAVA ) 最短路径算法(二)–DijkstraFloyd-Warshall单源、多源最短路径(JAVA ) 最短路径算法(三)–[ 带负权值图 ]Bellman-Flod的解法(JAVA )
  • 深度优先搜索(DFS) class Solution { public: //时间复杂度:O(MN), 其中MN分别为行数列数。... //空间复杂度:O(MN), 在最坏情况下,整个网格均为陆地,深度优先搜索的深度达到MN。 int numIslands(vector&l...
  • 如果是一个规模为2的n次方的问题,那么BFS时间复杂度是2的n次方,而DFS时间复杂度是n。 一般用BFS来解决迷宫的最短路径问题,这是因为DFS走到终点的时候可能是绕了一大圈才到达终点。 BFS 1.空间大,是呈指数...
  • BFS和DFS的区别

    2019-08-20 17:55:18
    时间复杂度BFS相对好一点 空间复杂度DFS相对好一点 而我们要怎样选择呢? 这很简单,DFS代码短,如果数据范围小则选DFS,反之选BFS
  • 时间复杂度速查表

    千次阅读 2014-10-11 22:25:26
    常用算法数据结构的...空间复杂度     平均 最差 最差 深度优先搜索 (DFS) Graph of |V| vertices and |E| edges - O(|E| + |V|) O(|V|) 广度优先搜索 (BFS) Graph of |V| vertices
  • 空间复杂度     平均 最差 最差 深度优先搜索 (DFS) Graph of |V| vertices and |E| edges - O(|E| + |V|) O(|V|) 广度优先搜索 (BFS) Graph of |V| vertices and |E| edges - O(|E| + |V|) O(|V...
  • 空间复杂度     平均 最差 最差 深度优先搜索 (DFS) Graph of |V| vertices and |E| edges - O(|E| + |V|) O(|V|) 广度优先搜索 (BFS) Graph of |V| vertices and |E| edges - O(|E| + |V|)...
  • 常用算法数据结构的...空间复杂度     平均 最差 最差 深度优先搜索 (DFS) Graph of |V| vertices and |E| edges - O(|E| + |V|) O(|V|) 广度优先搜索 (BFS) Graph of |V| vertices a
  • 常用算法数据结构的...空间复杂度     平均 最差 最差 深度优先搜索 (DFS) Graph of |V| vertices and |E| edges - O(|E| + |V|) O(|V|) 广度优先搜索 (BFS) Graph of |V| vertices
  • 通过深度优先搜索(DFS)、宽度优先搜索(BFS)、A*搜索算法来求解 (n^2 -1) 数码难题,要求如下: 初始状态以及目标状态形如下图。 输出完整的从初始状态到目标状态的动作序列。 对比3种算法的时间空间消耗。 ...
  • 众所周知,DFS和BFS除了功能上的差异,还有就是在时间空间复杂度的侧重点不同,DFS时间复杂度要高一些,BFS空间复杂度要高一些。有利就有弊,针对这些特点有着不少的优化版本。主要包括:双向BF
  • 算法之BFS算法框架

    2021-01-03 04:33:52
    BFS相对于DFS最主要的区别在于:BFS找到的路径一定是最短的,但是空间复杂度DFS要大很多。 BFS算法的核心思想实际上就是将问题抽象成“图”,从一个点开始,向周围扩散。一般来说,我们写BFS算法常用的数据结构是...
  • 数组集合的搜索

    2021-04-22 15:26:18
    DFSBFS一般把对象空间搜索一遍就能得到答案,比较复杂的问题往往复杂度在于如何高效剪枝, 而数组集合的搜索,往往搜索一遍还得不到答案, 比如寻找2个数的为给定数的所有数对,需要两层的嵌套搜索,暴力...
  • 数据结构算法

    2020-07-31 13:51:55
    算法 排序 简单排序 冒泡排序 插入排序 希尔排序(插入排序的改进) 选择排序 堆排序(选择排序的改进) ... 深度优先搜索DFS 广度优先搜索BFS ... 空间复杂度 是否稳定 冒泡排序 Ω

空空如也

空空如也

1 2 3 4
收藏数 61
精华内容 24
关键字:

dfs和bfs时间空间复杂度