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

令和5年度午後問3プログラミングの解法がまだ出ておりませんので以下のものであっているか確認をお願いしたいですm(_ _)m
特にオーダー法にする前の計算についてはよくわかっていないので、合っている自信が無いです。有識者の方がいらっしゃれば教えて頂けると嬉しいです?

－－－－－－－－－－－－－－－－－－－－－－

設問1
ア:n
イ:log2(n)

関数searchを1度呼び出す度に計算する回数は最大で4回(if文で)

葉を除く全てのノードについて左右どちらかだけに子ノードが存在する場合且つ、左右対称の場合ノード数と探索回数の関係は(ノード数n, 探索回数)

(3,4)
(5,8)
(7,12)
(9,16)
…

となっており、ノード数と探索回数の関係式は

2(n-1)

となった。オーダー法にすると

O(n)

よって
ア:n

全ての葉の深さが等しい完全な2分探索木のノード数と探索回数の関係は(ノード数n, 探索回数)

(3,4)
(7,8)
(15,12)
(31,16)
…

となっており、ノード数と探索回数の関係式は

4(log2(n+1)-1)

となった。オーダー法にすると

O(log2(n))

よって
イ:log2(n)

設問2
(1)
ウ:h1が2と等しい
エ:height(t,left,right) - height(t,left,left)
オ:h1が-2と等しい
カ:height(t,right,left) - height(t,right,right)

17ページ(1)の内容通りに解くとウ、エとなり、
(2)の内容通りに解くとオ、カとなった。

(2)
図1にinsert(r, 4)を適用し、
次にinsert(r, 8)を適用すると回答通りとなった。

(3)
キ:log2(n)

関数insert+関数balanceの計算回数を足すことで関数insertBの計算回数を出した。
ツリーの作成には関数insertBを使用していると仮定し、全ての葉の深さが等しい完全な2分探索木が生成されているとすると、関数insertは関数searchと同じ計算回数であると考えられる。よって、以下のようになる。

4(log2(n+1)-1)

関数balanceの計算回数は最悪5回(hの算出(heightの呼び出しは含まない)、if、elseif)

関数balanceが呼び出される回数はinsertBが呼び出される回数と等しいことより、最悪の計算回数
は、

4(log2(n+1)-1)(1+5)
= 24(log2(n+1)-1)

オーダー法にすると

O(log2(n))

よって
キ:log2(n)