知识卡片

普通读书笔记卡 · 6269.b

分支深度共同决定遍历规模

理解等级:中级

无重复的完整b叉展开到深度d,节点总数为1+b+…+b^d;b>1时其增长量级为O(b^d),不是b乘d。b=5、d=2共有31点,表5-1与图线展示深度增加的快速增长;有限已知图在去重遍历下则可按节点和边规模分析,不能把树式展开估计混称所有图的精确节点数。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 2 处

    • · 查看原书依据

      31个节点:根节点、根节点的5个相邻节点以及这5个相邻节点的5个相邻节点。表5-1展示了bd在b和d的规模都比较小时是如何增长的。 表5-1:不同层数的图的分支数的计算 图5-1:在广度优先搜索中,每进行一步就扩展一层,直到达到最大层数或者满足其他的终止条件 图5-2形象地展示了表5-1中的值。 图5-2:随着广度优先搜索的层数增加而增加节点数 尽管前面主要

    • · 查看原书依据

      超级节点。超级节点是那些具有很高出度的节点,它消耗计算机资源以及API请求以致到达访问速率上限的速度很快。至少在你初始分析时,你控制图中每个待获取用户的关注者的最大数量是可取的。因此你可以知道你面对的困难是什么,并可以断定在解决特定问题时,那些超级节点是否值得付出时间和精力。探索一个未知的图是一项复杂的(和令人兴奋的)问题,并且其他类型的多种工具,如采样技术

    参考来源

    - 位置:《社交网站的数据挖掘与分析(原书第2版)》第5章《5.2.1 网页爬取中的广度优先搜索》(spine93;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part0082.html;u075-ch05-008)。 - 结论依据:原文在“31个节点”附近的定义、例子或代码支撑本卡核心说明:无重复的完整b叉展开到深度d,节点总数为1+b+…+b^d;b>1时其增长量级为O(b^d),不是b乘d。边界按已读前提解释;示例未执行。 - 原始内容:31个节点:根节点、根节点的5个相邻节点以及这5个相邻节点的5个相邻节点。表5-1展示了bd在b和d的规模都比较小时是如何增长的。 表5-1:不同层数的图的分支数的计算 图5-1:在广度优先搜索中,每进行一步就扩展一层,直到达到最大层数或者满足其他的终止条件 图5-2形象地展示了表5-1中的值。 图5-2:随着广度优先搜索的层数增加而增加节点数 尽管前面主要 - 位置:《社交网站的数据挖掘与分析(原书第2版)》第9章《9.22.3 讨论》(spine148;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part0137.html;u225-ch05-008)。 - 结论依据:高出度节点可迅速扩大请求数;限制每点邻居数会同时改变所观测图。 - 原始内容:超级节点。超级节点是那些具有很高出度的节点,它消耗计算机资源以及API请求以致到达访问速率上限的速度很快。至少在你初始分析时,你控制图中每个待获取用户的关注者的最大数量是可取的。因此你可以知道你面对的困难是什么,并可以断定在解决特定问题时,那些超级节点是否值得付出时间和精力。探索一个未知的图是一项复杂的(和令人兴奋的)问题,并且其他类型的多种工具,如采样技术