設問４「コ」にはいる空欄をN(log2(σ)+1)だと思って解答したら、答えがNlog2(σ)でした。
納得いかなく、答えが間違っていて、N(log2(σ)+1)が本当の正解ではないかと思っています。

誰か教えてください。

応用情報 平成30年 秋期 午後 問3
https://www.ap-siken.com/kakomon/30_aki/pm03.html

いいえ，N×log2(σ)が正しいです。

次のスレッドの plさんの発言 No.6 を参照。
https://www.ap-siken.com/bbs/1621.html

> オーダ(なんとオーダーOrderのこと)では、1回も100回も同じことです。
> 1万回でも1億回でも、それが整数値で無限でなければ
> コンピュータにとって些細な事だからです。
> 
> n回比較する作業を、何回すれば良いでしょうか。
> n-1回なので、それはn回に等しいです。
> n回の比較をn回繰り返すから、n^2。これがオーダになります。
> 
> ちなみにn^2+nの場合、n^2以外の項は無視されます。
> これはn^2にとってnが些細過ぎる数だからです。

この投稿は投稿者により削除されました。(2024.10.09 18:36)

聞かれているのがウェーブレット木だからです。

問題文の図1左側のビット数の総和を求める必要があります。

つまり、σ=4だと深さが1で終わります。

だから、σ=4、N=10だと図1の左の通りになりビットの総和は20。

これを一般化すると解答の通りとなります。

私の勝手な推測ですが、ええいああさんは求めるべきビット数は、「1・0を全て振り分け切った」つまり「図1のウェーブレット木の更に1つ深いところまでの総和を求める必要がある」と思い、解答の式にしたのかなと思います。

私も引っかかりました。難しいですね。

こはさん、おっしゃる通りです。
ビットを全て振り分け切ったもので解答してしまいました(図1の右のように)。

そこで、気になってしまったのですが、ウェーブレット木とは、図1を例にすると図1左の形が完成形ということでしょうか。

問題文を見てみるとウェーブレット木の構築(3)では、文字列が1種類になるまで分解しているのですが、これはあくまで文字列に対する操作であってウェーブレット木での操作ではないという理解で合ってますか。

ご返信お待ちしております。

> そこで、気になってしまったのですが、ウェーブレット木とは、図1を例にすると図1左の形が完成形ということでしょうか。

そうなんだと思います。

根拠としては、ウェーブレット木構築手順の(3)にある記述です。
------------------------------------------------------------------------
  ビットの値が0の場合に取り出した文字列内の文字が2種類以上の場合は，その文字列に対応する新たなノードを生成して，左の子ノードとする。取り出した文字列内の文字が1種類の場合は，新たなノードは生成しない。
  ビットの値が1の場合に取り出した文字列内の文字が2種類以上の場合は，その文字列に対応する新たなノードを生成して，右の子ノードとする。取り出した文字列内の文字が1種類の場合は，新たなノードは生成しない。
------------------------------------------------------------------------

文字列"CTCGAGAGTA"を考えると、図1のウェーブレット木の深さ1の左のノードの場合、「11000」の1番目の「1」と2番目の「1」はともに「C」になります。
先程の文章を読む限り、「取り出した文字列内の文字が1種類の場合は，新たなノードは生成しない。」ということですので、深さ1から更に深いノードは生成されないということになります。

ですので、完成形という認識で問題ないのかと思います。

うまく説明できてるかわかりませんが、気になる点がありましたらご指摘ください。

> 問題文を見てみるとウェーブレット木の構築(3)では、文字列が1種類になるまで分解しているのですが、これはあくまで文字列に対する操作であってウェーブレット木での操作ではないという理解で合ってますか。

図1の文字列の振り分けでは、最終的には「各文字列が1種類ずつ」になるように振り分けられています。
この図1の直前の記述
「また，図1の文字列の振り分けは，ウェーブレット木によって文字列Pが振り分けられる様子を示している。」

上記の内容から、図1にある文字列の振り分けは「あくまで文字列に対する操作であってウェーブレット木での操作ではない」という理解で良いと私も思います。

気になる点があればご指摘いただけると幸いです。

No.4～No.8 の論点がズレているので再度発言します。

問題文を見なくても，アルゴリズムが何だろうと，
N×(log2(σ)＋1)
の ＋1 を書いている時点で，計算量（オーダ）の解答として不正解です。理由はNo.2で述べました。

計算量（オーダ）という概念を知らないのなら，ネット検索すれば解説がいくつもみつかるでしょう。

空欄「コ」で聞かれていることは「キー値のビット列の長さの総和」ですので、論点はずれていないかと思います。

計算量を求める問題(今回の問題だと空欄「ケ」、「コ」)であれば、オーダー記法に則り、端数は除いた表記にはなります。

いかがでしょうか。

ごめんなさい，オーダに関する問いは ケとク で終わっており，コ は違うのですね。
No.2とNo.9は読み捨ててください，たいへん失礼いたしました。

jjon-comさんの、計算量に関するお話も、再確認する良いきっかけになりました。No.2の時スルーしてしまいごめんなさい。

こはさん、理解できたと思います。本当にありがとうございました。おそらく今回の試験にウェーブレット木はでることはないと思うのですが、問3は本番でも解こうと思っているので、自分が思い込んだ解き方でなく、問題文をしっかり読んで解こうと思います。

お二方、大変ありがとうございました。
夜分に失礼しました。

日曜日頑張ってきます！