0
아래의 각 절차에 대해 T (n)을 실행 시간이라고합시다. T (N) (즉, F를 찾을 수 (N)의 순서를 찾기 T (N) ∈ N (F()).재귀 이진 검색의 실행 시간을 찾는 방법은 무엇입니까?
Procedure BinarySearch(table T [a . . . b], int k):
if a > b then
return -1
end if
middle ← ⌊(a + b)/2⌋
if T [middle] = k then
return middle
end if
if k < T [middle] then
return BinarySearch(T [a . . .middle], k)
else
return BinarySearch(T [middle . . . b], k)
end if
내가 간단한 기능 만이 이후 실행 시간을 찾아하는 방법을 알고 같은 내가하는 데 문제 때문에 재귀 호출이 포함되어 있습니다.
당신이 그것에 대해 생각하면 조금, 당신은 –
당신이 T (n)을 가지고 있다고합시다. 각 T (n)에 대해, 당신은 반으로 나누었습니다. 그래서 T (n/2). 얼마나 많은 시간이 필요합니까? 너는 n 시간 안에 나눌 수 있니? 알프? @ H2CO3의 의견보기. –
가상 코드에 버그가 있습니다. a = 1, b = 2, T [2] = k로하자. 그런 다음 middle = (a + b)/2 = 1 및 k> T [1]. 재귀 적으로 BinarySearch (T [1 ... 2], k)를 호출합니다. "BinarySearch (T [a.m.-1], k)"와 "return BinarySearch (T [middle + 1 .b], k)"로 의사 코드를 변경하는 것이 좋습니다. T [중간]을 이미 확인 했으므로 다시 확인하는 것은 의미가 없습니다. –