我正在使用主定理计算以下函数的平均情况复杂度:
T(n) = 2T (n/2)+ n/ log n
根据http://people.csail.mit.edu/thies/6.046-web/master.pdf中的问题7,
上面写着 不适用(f(n)和n log b a 之间存在非多项式差异) 此答案也支持这个答案。
然而,在这个视频中,讲师在12:26解决了同样的问题,他得出了答案。
Θ(nloglogn)
能有人解释一下哪一个是错误的,以及为什么吗?
我正在使用主定理计算以下函数的平均情况复杂度:
T(n) = 2T (n/2)+ n/ log n
Θ(nloglogn)
能有人解释一下哪一个是错误的,以及为什么吗?
第0级有1个值为 n / log(n) 的节点。
第1级有2个值为 (n / 2) / log(n / 2) 的节点。
...
第i级有2i个值为(n / 2i) / log(n / 2i)的节点
简化后,第i级贡献了n / (log(n) - i)。
请注意,一共需要到达~log(n) - 1个级别才能到达一个常数。