因为在基于比较的排序模型中，完成n个元素的排序，其最坏情况下

[问答题]

因为在基于比较的排序模型中，完成n个元素的排序，其最坏情况下需要 $\Omega(nlgn)$ 时间。试证明：任何基于比较的算法从n个元素的任意序列中构造一棵二叉搜索树，其最坏情况下需要 $\Omega(nlgn)$ 的时间。

yycode

反证法：假设构造一棵二叉搜索树的最坏情况的时间 T( n ) < c1nlgn，而中序遍历二叉搜索树只需要 Θ( n ) 的时间，所以通过构造二叉搜索树的比较排序时间为 T( n ) + O( n ) < c2nlgn，与基于排序模型中，n 个元素的排序最坏情况的 Ω( nlgn ) 时间矛盾。假设不成立。得证

发表于 2020-11-05 09:00:11 回复(0)