以下算法的遞推關係是什麼？

T（n）= T（n-1）+ 2 + T（n + 1）以下是遞歸關係嗎？
我只是指望中間變量賦值和最後一行，因爲所有的if語句都排除了其他的......這種方法是否正確？以下算法的遞推關係是什麼？

/* 
* V is sorted 
* V.size() = N 
* The function is initially called as searchNumOccurrence(V, k, 0, N-1) 
*/ 
int searchNumOccurrence(vector<int> &V, int k, int start, int end) { 
    if (start > end) return 0; 
    int mid = (start + end)/2; 
    if (V[mid] < k) return searchNumOccurrence(V, k, mid + 1, end); 
    if (V[mid] > k) return searchNumOccurrence(V, k, start, mid - 1); 
    return searchNumOccurrence(V, k, start, mid - 1) + 1 + searchNumOccurrence(V, k, mid + 1, end); 
}

來源

2017-05-09 marcoshass

這是一個二進制搜索？ – Cameron

看起來像[二進制搜索]（https://en.wikipedia.org/wiki/Binary_search_algorithm）。雖然要計算具有特定值的元素數量，但我認爲只要找到一個匹配元素就可以掃描周圍的元素。 – ilkkachu

複雜性不是你提到的。它是T（n）= 2 * T（n/2）+ c。 –

正如@GAURANG VYAS在評論中提到的那樣。遞歸關係是T（n）= 2 * T（n/2）+ O（1）並且在Theta（n）中。由於您的方法searchNumOccurrence()查找給定k的所有匹配項，它可能會查看所有的匹配項五中的元素。典型例子，如果V中的所有元素都等於k。

來源

2017-05-09 20:14:23 gue

以下算法的遞推關係是什麼？

回答

相關問題