0

再帰的線形検索の複雑さを分析したかった (分割統治法を使用)。log(n) ですか、それとも n ですか? log(n) でない場合、実際の複雑さとは何ですか?

int linear_search(int *a,int l,int h,int key){
    if(h == l){
        if(key == a[l])
            return l;
        else 
            return -1;
    }       
    int mid =(l+h)/2;
    int i = linear_search(a,l,mid,key);
    if(i == -1)
         i = linear_search(a,mid+1,h,key);
    return i; 
}
4

3 に答える 3

2

はい、O(n)です。しかし、このアルゴリズムには意味がありません。あなたがしなければならないのは、配列を調べて、このアルゴリズムが行っていることである要素が見つかったかどうかを見つけることですが、それは不必要に複雑です.

于 2012-07-09T06:09:55.117 に答える
0

はい、配列内のすべての値を検索して見つけます。その時間の複雑さは omega(n) です。lg(n) にあるように見えますが、 if(h == l) のため、配列のすべての値を検索します

于 2012-07-09T06:23:08.753 に答える
0

はい、O(n) です。再帰メソッドが行うことは単なるループであるため、実際のループを使用する方がよいでしょう:

int linear_search(int *a,int l,int h,int key){
  for (int i = l; i <= h; i++) {
    if (a[i] == key) return i;
  }
  return -1;
}

ループを回避するために再帰を使用したい場合、再帰を示す (悪い) 例で時々見られる、より悪い方法が 1 つあります。

int linear_search(int *a,int l,int h,int key){
  if (l > h) {
    return -1;
  } else if (a[l] == key) {
    return l;
  } else {
    return linear_search(a, l + 1, h, key);
  }
}

それでも O(n) ですが、配列が大きすぎるとスタックがいっぱいになるため、さらに悪化します。分割統治アプローチは、少なくとも整数のビット数より深く入れ子になることはありません。

于 2012-07-09T06:27:26.997 に答える