アレイのアクセス数を最小限に抑えるには

-1

アレイにアクセスする瞬間にアレイにアクセスする時間を2倍に減らすにはどうすればよいですか？ユーザーが入力したシーケンス番号の中で最大の番号を見つけるにはアレイのアクセス数を最小限に抑えるには

int i=0; 
    int max = -1; 
    int a_i = -1; 

    for (i=0; i<length; i++) 
    { 
    a_i = array(a,i); 

    if (a_i > max) 
    { 
    max = a_i; 
    } 

    return max;

完全なコードon pastebin

任意のヘルプ高く評価しました。

出典

2012-05-04 UnknownUser

コードすることができ、O（n）との複雑さである、一度だけ、配列の各要素にアクセスするように思われます。配列がソートされている場合は、バイナリ検索を使用して複雑さをO（logn）に減らすことができます。 –

@AdamLiss：ソートされている場合、コードは値の配列の中で最大値を見つけているので、O（1）です。しかし、これはOPが求めていることではありません。正直言って、OPがどのような問題を抱えているのかわかりません（欠落した '} 'を考慮して）コードを見れば、配列へのアクセスは1回しかないと思います。 – Skizz

あなたはブレースを見逃しているようですか？ –

短い答えあなたはカント

、あなたは、配列についての情報がない考慮して、すべての項目を反復処理する必要があります。

長い答え

あなたは見つけるためにあなたが（everyting）を挿入するO(n)を必要とするアレイとO(n)を使用して

前にいくつかの時間を失う受け入れる場合は、読み出し時のアクセスの量を減らすことができます

minimum heapを使用すると、実際に検索する時間を短縮することができれば、オーバーヘッドがありますインサートO(n log(n))でO(1)が必要です。あなたはまた、検索する前に、配列をソートでき

、これはO(n log n)

出典

2012-05-04 15:57:46 Pierre

アレイのアクセス数を最小限に抑えるには

答えて

関連する問題