-1

宿題について次の質問がありますが、どのようにアプローチすればよいかわかりません

次の並べ替えアルゴリズムがあるとします。

サイズ N(A[1…N]) の配列をソートするために、アルゴリズムは次のことを行います。

  1. 再帰的に、最初の N-1 要素 A[1…N-1] を並べ替えます
  2. 二分探索を使用して A[N] の正しい場所を見つけ、それをソート済みリストに追加します。正しい場所を見つけたら、値をシフトして A[N] の場所を作る必要があります。

このアルゴリズムの詳細な再帰方程式を書きます (項を省略しないでください)。

4

2 に答える 2

2

ここに画像の説明を入力

C定数はどこにありますか。

n > 1この場合の各用語の由来を見てみましょう。

  • T_{n - 1}

再帰的に、最初の N-1 要素 A[1…N-1] を並べ替えます

  • ログ n

二分探索を使用して A[N] の正しい場所を見つけ、それをソート済みリストに追加します

  • n

正しい場所を見つけたら、値をシフトして A[N] の場所を作る必要があります。

于 2013-03-29T22:03:00.937 に答える
1

T(n) を、n 要素の配列について記述されたアルゴリズムの実行時間とします。まず、最初の n-1 要素で再帰的に自分自身を呼び出し、T(n-1) のコストを与えます。次に、バイナリ検索を使用して元の位置 n の要素の位置を見つけるため、log(n-1) 時間かかります。最後に、要素 (最大 n-1 個) をシフトして、新しい要素のためのスペースを確保します。これには、最大 n ステップが必要です。

ピースをまとめると、T(n) <= T(n-1) + log(n-1) + n - 1 が得られます。最後に、基本ケースを指定しなかったため、アルゴリズムは何もしないと想定しています。空のリストで（したがって、簡単に並べ替えます）、T（0）= 0を取得します。

于 2013-03-29T20:59:03.397 に答える