在用回溯法解题时,若解空间树中从根节点到叶节点的最长路径为h(n),则显式地存储整个解空间树所需空间通常为O(2h(n))或()。
A: O(2h(n))
B: O(h(n)!)
C: O(h(n))
D: O(n2)
A: O(2h(n))
B: O(h(n)!)
C: O(h(n))
D: O(n2)
举一反三
- 用回溯法解题的一个显著特征是在搜索过程中动态产生问题的解空间。在任何时刻，算法只保存从根结点到当前扩展结点的路径。如果解空间树中从根结点到叶结点的最长路径的长度为h（N）,则回溯法所需的计算空间通常为（） A: O（n） B: O（n2） C: O（h（n）） D: O（h（n）+n）
- 二叉搜索树的高度h和节点个数n满足关系 A: h=O(1) B: h=O(lgn) C: h=O(n) D: h=O(nlgn)
- 回溯法与分支限界法的空间复杂度是相同的，都是O(h(n)), h(n)是解空间树的深度。 A: 正确 B: 错误
- 用父节点+孩子节点的方法存储n个节点的树,需要的空间是: A: O(1) B: O(n) C: O(nlgn) D: O(n^2)
- f(n)=O(g(n)). g(n)=O(h(n)) 则h(n)=O(f(n))