11

私はこのことにかなり慣れていないので、あなたの助けが必要です。

1、2、... n の繰り返しを含む、サイズが n の配列の最大値を返す効率的な単純なアルゴリズムを構築する必要があります。

次に、最高の実行時間、平均実行時間、最悪の実行時間を決定する必要があります。

だから私は2つの質問があります：

  1. まず第一に、この単純なアルゴリズムに効率的なソリューションを要求するという考えが何であるかを理解しようとしています。私が理解している限り、1 から n までの単純なループのみを使用して、最大値を探す必要があります。「効率的な」アルゴリズムは、配列内の値 n を見つけた場合、これが配列内の最大値であるため、それ以上の値の検索を停止できることを指摘していますか?

  2. 平均実行時間を計算する際に、一様分布であるという事実を使用して、最適な実行時間と平均実行時間を決定するにはどうすればよいですか。つまり、配列内の各セルは、1/n の確率で最大値になります。

よろしくお願いします！

4

4 に答える 4

8

最良の場合-最初の（）として最大要素を見つけO(1)、最悪の場合-それはチェックされた最後の要素です（O(n)）。

トリッキーな部分は平均的なケースです。
平均的なケースを見つけるには、予想される反復回数が必要です。

最大値を見つけたら停止できるため、問題を2つの部分に分割できます。

  1. [0,n-1)：平均して（各要素の均一な独立分布を想定）-数nは各場所に1 / nの確率があるため、この部分の予想される反復回数は1/n + 2*((n-1)/n)/n + 3 * ((n-1)/n)^2/n + ... + (n-1) * ((n-1)/n)^(n-2)/n 1です
    。上記の式は、次のような醜い式を生成します。O(n)
  2. 最後の要素は、最初のn-1要素に値が含まれていないかどうかがチェックされますn：したがって、上記に追加する必要があります。n* ((n-1)/n)^(n-1)これO(n)も同様です（limからinfinityは1/e * n）。

O(n)これは、平均時間ソリューションで合計されます。

（1）：各要素の式は次のj*((n-1)/n)^(j-1) * (1/n)理由によります：

  • j-チェックされた要素の数（反復回数）
  • ((n-1)/n)^(j-1)n-前の要素にない確率
  • (1/n)-この数がである確率n。
于 2012-10-31T14:18:03.723 に答える
3

配列に関する事前情報がない場合 (たとえば、並べ替えられている場合)、最悪の場合も最良の場合もありません。最大値を見つけるためにすべての要素をスキャンする必要があり、O(n) 回かかります。

また、各セルの最大値を取得する確率分布を知ることは、一般的には役に立ちません (検索スペースを縮小しない限り。たとえば、一定数のセルのみが最大値を取得する確率がゼロではないことがわかっている場合は、これらのセルを検索する必要があり、一定の時間がかかります)。したがって、一般的に

最良の実行時間 = 最悪の実行時間 = 平均実行時間 = O(n)

于 2012-11-01T03:11:48.253 に答える
2

アルゴリズムは次のように機能します。最初に数値を選択します (この場合、配列の最初の数値を選択し、それが最大値であると仮定して、それを次の数値と比較し、それが大きい場合はそれを新しい最大値とします) 、配列での検索が完了するまで)、次のコードは C です。

#include <stdio.h>
#define SIZE 100

typedef struct{
    int val;
    int loc;
} find;

/* Functions declaration (Prototype) */
find maxFinder( int * const a );

int main( void )
{
    int response[ SIZE ]=
       { 1, 3, 5, 7,  8, 9, 0, 10, 65, 100,
         1, 3, 5, 7,  8, 9, 0, 10, 65, 100,
         1, 3, 5, 7,  8, 9, 0, 10, 65, 100,
         1, 3, 5, 7,  8, 9, 0, 10, 65, 100,
         1, 3, 5, 7,  8, 9, 0, 10, 65, 100,
         1, 3, 5, 7,  8, 9, 0, 10, 65, 100,
         1, 3, 5, 7,  8, 9, 0, 10, 65, 100,
         1, 3, 5, 7,  8, 9, 0, 10, 65, 100,
         1, 3, 5, 7,  8, 9, 0, 10, 65, 100,
         1, 3, 5, 7,  8, 9, 0, 10, 65, 100 };

    printf( "The max number is %d located in the index %d.\n", maxFinder( response ).val, maxFinder( response ).loc );
    return 0;
}

 find maxFinder( int * const a )
 {
    /* Local Variables initialization & declaration */
    int i;
    find result;

    result.loc = 0;
    result.val = *( a + 0 );

    for( i = 1; i < SIZE; i++ ){
        if ( result.val < *( a + i ) ){
            result.loc = i;
            result.val = *( a + i );
        }
    }
    return result;
 }
于 2012-10-31T14:06:30.133 に答える
1

最悪のケースと最良のケースは単純です。平均的なケースはより興味深いものです。ウィキペディアの幾何分布のページを見てください。

于 2012-10-31T14:02:23.810 に答える