応用情報技術者 試験情報＆徹底解説

解説では、
O(log(n))となっています。
これは、
O(log(n+1))ではないかと思い腑に落ちません。

というのも、
完全2分木であるならば、
n=1,3,7,15,・・・
比較回数＝1,2,3,4,・・・
となると思います。

これを数式化すると、
比較回数＝log2底の(n+1)
となるので、O記法を適応すると、
O(log(n+1))

ではないでしょうか。
ご回答よろしくお願いいたします。

この投稿は投稿者により削除されました。(2022.09.03 19:44)

スレ主です。
補足です。

こちらは午後問題で、
完全２分木の最大比較回数の問題です。

私が質問で書いた式の導出方法に間違いがあるでしょうか。

それとも、オーダーnが限りなく
増加すれば、＋１は無視できるから、
という理由でしょうか。

もしそうなら、
解説にのっていた導出方法について質問が湧くのですが、
なぜ、そちらだと
2底のlog(n)が直接導けているのでしょうか。

>それとも、オーダーnが限りなく
>増加すれば、＋１は無視できるから、
>という理由でしょうか。

これについては、その通りで
n+100でも、5nでも
オーダーは、O(log(n))です。オーダーというのはそういうものだと思ってください。
ちなみにオーダーでよく登場するのは、O(n^2),O(n),O(log(n))の３つです。

>解説にのっていた導出方法について質問が湧くのですが、
>なぜ、そちらだと
>2底のlog(n)が直接導けているのでしょうか。

まず解説文の解釈ですが、ケに関しては、比較回数という言葉は使っていません。
>n個のノードを1／2することをk回繰り返して、1つの値を見つけます。
と書いてあります。ここで出てくるkは、深さを表していると思います。


nを2のべきで考えると

n=1   2^0   k=0 0回で1つになる  深さ0の行 (1)
n=2   2^1   k=1 1回で1つになる  深さ1の行（2,3）
n=4   2^2   k=2 2回で1つになる  深さ2の行（4,5,6,7）
n=8   2^3   k=3 3回で1つになる  深さ3の行（8,9,10,11,12,13,14,15）
n=16  2^4   k=4 4回で1つになる  深さ4の行（16,.........,31）
＊＊＊k=log(n)です。
深さが同じ行にある数は、比較回数が同じになる仲間です。(2分木の場合)
また、比較回数＝深さ＋１  なので

k+1が、対応するnの比較回数になります。
例えば、n=15ならば、3+1=4 で  4回

スレ主様の
n=1,3,7,15から
n+1=2,4,8,16を求めて2^kで表し、kを比較回数にするのは、同じ結果になりますね。

この投稿は投稿者により削除されました。(2022.09.05 19:09)

boyonboyon  様

なるほど。オーダーってそいういうことなんですね。
O記法は、プログラミングの処理量の評価に使われるもので、
桁数がわかればいいから、係数とか諸々は無視できる、と。
なので、おっしゃるようにO(n^2),O(n),O(log(n))のパターンを押さえておけば
大体は対処可能そうですね。

解説文の解説もしていただき有難うございます。
比較回数ではなく、k(深さ)を使用してましたか。

確かに、比較回数を深さで置き換えても
問題なく成り立ちそうですね。

・n(ノード数)=1,3,7,15・・・
・k(深さ)=0,1,2,3・・・
・最大比較回数＝k+1

なので、

①n+1=2^k (n≠1)
②n=2^k (n＝1)

①n≠1の場合
2底のlog(n+1)=ｋ
2底のlog(n+1)=最大比較回数-1
O（log(n)）=  最大比較回数のオーダー

②n＝1の場合
2底のlog(n)=ｋ
2底のlog(n)=最大比較回数-1
O（log(n)）= 最大比較回数のオーダー

∴O（log(n)）= 最大比較回数のオーダー


スッキリしました。
有難うございました！