algorithm - 递归线性搜索(使用分而治之技术)的复杂性是多少？

Question

想分析递归线性搜索的复杂性(使用分治法)。是 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; 
}

Answer 1

是的，它是 O(n)。但是这个算法没有意义。您所要做的就是遍历数组并查找是否找到了元素，这就是该算法正在做的事情，但它不必要地复杂。