32.

首先104的32题的第二个选项
这种给固定数量elements要做几次comparison需要怎么算呢
24.

105的24题的(c)(d)选项
虽然说这题之前有蛮多人讨论过了
但是仍然很不理解为什么(d)说用non-linear可以突破 nlogn
不是一定要linear sorting才能办得到吗？
然后(c)主要是不知道decision tree前面加一个linear是什么意思
48.

48题的(c)选项
怎么看到林立宇讲义上面105页是写说用binary heap单步骤进行decrease key
的确是 logV 的时间啊？
还是我的观念有错吗？
谢谢大家帮解惑^^

第一题decision tree解 你上面不就有写了

48(c) log V 应该没错24 题比较难一般的 sorting lower bound 是用 comparison 证明的但是 linear decision tree model 也可以证明https://algs4.cs.princeton.edu/65reductions/所以 24 (c) 要看你怎么解释linear decision tree 的 lower bound 会 implycomparison model 的 lower bound但是大部分课本上都是只证明 comparison model 的..24 (d) 的话 因为 non-linear 可能会提供 extra power所以有可能可以 beat O(n lg n)

回水饺大大是的，但是不知道这样是不是对的因为那个应该是ave. case，但是题目是问worst case谢谢F大这么详尽的讲解

说个题外话 你知道贴图片不是复制那个网址吗