私は試験で非常に紛らわしい問題に直面し、それを間違って試みました.4つのオプションが与えられた客観的なタイプの問題でした.今では正しいオプションを知っていますが、説明はありません.
問題 ：
heapsort を使用して Ɵ(logn) 時間でソートできる要素の数は
a) Ɵ(1)
b) Ɵ(√ log n)
c) Ɵ(log n / loglog n)
d) Ɵ(log n)
選択肢 c は正しいです。
私はオプション a) を選択していましたが、ログ n 時間で 1 つの要素のみがソートされると思っていました。それは間違っていました。なぜオプション c) が正しいのかわかりません。
t=exp(n) を時間、m をその時間内にソートできるアイテムの数とします。
a) m = Θ(1) ⇒ t → ∞: 時間に関係なく、限られた数のアイテムしか並べ替えることができません。
b) m = Θ(√t) ⇒ t = Θ(m²): 二次時間が必要です。愚かなバブルソート。
c) m = Θ(t/log t) ⇒ t = Θ(m log m): これはヒープソートの複雑さです。
d) m = Θ(t) ⇒ t = Θ(m): 線形時間ソートは、真であるには良すぎます。
c) の変換は、ほとんど「直感」に基づいていることを告白しなければなりません。私はそれが正しいか、少なくとも「ほぼ正しい」と確信していますが、これを示すために使用した正式なルールは知りません。