ヒープソート 追加操作について

質問

配列を用いたヒープにデータを追加する。
この際、データの追加は配列の最後の要素に新たなデータを加え、ヒープ条件を満足するまで
親子間でデータの交換を行う。
要素数をnとしたら、この追加操作にかかる最悪時間計算量を求めよ。

この問題なのですが、ただ単にデータを一つ追加する際の最悪時間計算量だったら、
オーダlog n ですが、
追加する要素がnこだったら、n* log nになります。

この問題ではどちらがより適切なのでしょうか？
どなたかご教授ください。

回答No.2

axsies

プログラムの質問というより、日本語解釈の質問ですね…ｗ
まぁ、ヒープソートに関する問題ですし、問題文でヒープ追加操作のステップを説明している、
最悪の時間計算量を問うていることから、

空のヒープを用意し、n個の要素をヒープに追加する。
i番目の要素を追加するときの時間計算量はO(log i)だが、
n番目まで追加したとき、それまでの追加操作の中で最悪の場合（つまりn番目)のオーダーを求めよ。

というのが趣旨だと思われます。
というわけで、O(log n)が正解なのではないでしょうか。
ちょっと意図を汲みにくい問題文ですね。

回答No.1

Tacosan

とりあえず「何個のデータを追加するの?」って聞けばいいんじゃね?

でも, n個のデータを持つヒープに「一気に n個のデータを追加する」なら n log n じゃないよなぁ.