algorithm - 比較の二分探索数

Question

この再帰的なコードを、標準の二分探索アルゴリズム用に作成しました。比較カウンターに+1を追加するのはいつですか？以下の疑似コード

Inputs A: Array of Data;
key:Data; L,R:Integer;
Variables m:Integer;
Returns m:Integer;

Begin
If R<L then return -1; fi
m:= (R+L)/2
if key = A[m] then return m; fi
if key > A[m] then
return binSearch(A,key,m+1,R);
Else
return binSearch(A,key,L,m-1);
fi
End

最初のifステートメントでLとRをチェックすることは、比較としてカウントされますか？少し混乱しています。

Answer 1

比較と言うとき、厳密に if の数を意味するのではなく、二分探索の O(log(n)) の複雑さに到達しようとしていると思いますか? その場合は、関数の先頭でカウントして、行われた呼び出しの量をカウントしてみませんか

Answer 2

非対称分析では、条件文はO（1）と見なされます。

条件付き問題は決定問題だからです。0または1。