なんで

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

なんでですか？？

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)のとするのが普通なので、あまり考えられない。

この回答へのお礼

なるほど？？ありがとうございます

お礼日時：2024/06/08 17:42

No.2 回答者： Tacosan 回答日時： 2024/06/08 10:03

さすがに

あなたがなにをどう考えてどうだと思ったのか
を私が答えるのは不可能だなぁ.

どうしてできると思えるんだろう.

この回答へのお礼

ちがくて、どのような処理なのか、解析してください。

お礼日時：2024/06/08 11:35

No.1 回答者： Tacosan 回答日時： 2024/06/07 23:24

「長さｎの入力に対し０からｎー１までの連番を一時的に記憶する」というのがどのような処理なのかよくわからんのだが.

さておき, ではあなたはなにをどう考えてどうだと思った?

この回答へのお礼

それをたこさんがこたえるんだよ？？？
私が質問してるひとだから。

お礼日時：2024/06/08 09:13