おしえて

なんで

解決済

質問者：ゆゆにゃ。
質問日時：2024/06/07 18:00
回答数：3件

長さｎの入力に対し０からｎー１までの連番を一時的に記憶するのだからO(nlogn)の記憶容量を要する

なんでですか？？

通報する

この質問への回答は締め切られました。

質問の本文を隠す

回答 (3件)

ベストアンサー優先
最新から表示
回答順に表示

No.3ベストアンサー

回答者： kmee
回答日時：2024/06/08 15:01

「長さnの入力に対し0からn-1までの連番を一時的に記憶する」

を素直に考えれば記録容量はO(n)のはず。

それを log n 倍しているということは
O(logn)個の「長さnの入力に対し0からn-1までの連番を一時的に記憶」したものが必要だということ。

その文章の前に「 O(logn)個の連番が必要だ」という説明が無いですか?

あと考えられるのは、連番の一つを保存するのに O(logn)の記憶容量が必要 × 長さn =O(nlogn) というものですが(つまりは記憶容量をビットで数えている)
1つの数値を記憶するのに必要な記憶容量はO(1)のとするのが普通なので、あまり考えられない。