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;
}

如果您想使用递归来避免循环,则有一种更糟糕的方法,有时可以在显示递归的(坏)示例中找到:

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 回答