搜索,动态规划,二叉树的时间复杂度计算通用公式

搜索的时间复杂度:O(答案总数 * 构造每个答案的时间)

举例:Subsets问题,求所有的子集。子集个数一共 2^n,每个集合的平均长度是 O(n) 的,所以时间复杂度为 O(n * 2^n),同理 Permutations 问题的时间复杂度为:O(n * n!)

动态规划的时间复杂度:O(状态总数 * 计算每个状态的时间复杂度)

举例:triangle,数字三角形的最短路径,状态总数约 O(n^2) 个,计算每个状态的时间复杂度为 O(1)——就是求一下 min。所以总的时间复杂度为 O(n^2)

用分治法解决二叉树问题的时间复杂度:O(二叉树节点个数 * 每个节点的计算时间)

举例:二叉树最大深度。二叉树节点个数为 N,每个节点上的计算时间为 O(1)。总的时间复杂度为 O(N)

©著作权归作者所有,转载或内容合作请联系作者
【社区内容提示】社区部分内容疑似由AI辅助生成,浏览时请结合常识与多方信息审慎甄别。
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

相关阅读更多精彩内容

  • 搜索的时间复杂度:O(答案总数 * 构造每个答案的时间)举例:Subsets问题,求所有的子集。子集个数一共 2^...
    函仔阅读 7,365评论 0 0
  • 1. 树的概念 一个树由节点组成,这些节点包含根节点,父节点,子节点,兄弟节点;没有任何一个节点的树称为空树;如果...
    HChase阅读 11,619评论 0 34
  • 一些概念 数据结构就是研究数据的逻辑结构和物理结构以及它们之间相互关系,并对这种结构定义相应的运算,而且确保经过这...
    Winterfell_Z阅读 11,490评论 0 13
  • 树的基本概念 节点,根节点,父节点,子节点,兄弟节点都是属于树的范涛; 一棵树可以没有任何节点,称为空树; 一棵树...
    coder_feng阅读 4,894评论 0 0
  • 介绍 二叉树的结构 二叉树常考的原因有如下几点1、它可以结合链表、栈、队列和字符串等数据结构出题2、需要熟练掌握图...
    雨住多一横阅读 3,283评论 0 1

友情链接更多精彩内容