私はここに1つのアルゴリズムを持っています。それは何このアルゴリズムのランタイムを定義できません
Click here to check algorithm image
、それは、配列を横断し、3つの最大値を検索し、その合計を返します。 たとえば、配列[1,2,3,4,5]は12（3 + 4 + 5 = 12）を返します。
画像のアルゴリズムでは、O（nlogk）と表示されています。しかし、それは私が理解できないものです。
以下は、画像内のループの最初についての私の視点です：
ヒープの方法 "の挿入（）" と "deleteMin（）"、彼らの両方がかかるO（LOGN）。したがって、最初のforループでは、ランタイムを追加することによってO（2 * logn）を作成します。これは単にO（logn）です。最初のforループは配列内のすべての要素を反復するので、最初のforループの合計実行時間はO（nlogn）です。続き
は画像でwhileループ第二についての私の視点です：forループの前のから
、我々はh.size（）> kであれば最小値の一部を削除しました。したがって、ヒープ内の値の数は現在kです。ヒープの最小値を検索するとO（logn）が正しく認識され、 "h.deleteMin（）"にはO（logn）が必要なので、 "sum = sum + h.min（）"はO再度検索して削除してください。 O（2 * logn）はランタイムを追加するだけで、これは単にO（logn）です。これは、k個の要素があるのでk回だけ反復するので、2回目のwhileループはO（k * logn）になります。
したがって、最初のforループからO（nlogn） logn）から2番目のwhileループ。 kはある定数であるため、O（nlogn）はO（k logn）よりも大きいことは明らかです。したがって、このアルゴリズムは最後にO（nlogn）で終了する。
しかし答えは、 "O（nlogn）"ではなく "O（nlogk）"と答えています。
理由を説明できますか？