HOME»応用情報技術者試験掲示板»午後問のオーダ記法について
投稿する
午後問のオーダ記法について [5840]
こんにちはさん(No.1)
お疲れ様です。
表際の件について
午後問のプログラミングに出てくるオーダ記法を求めさせる問題が解説を読んでも理解できません。
1.解き方のコツはありますでしょうか。
2.掛ける労力に対してリターンが少ないので基本的なオーダ記法以外は捨て問とした方が良いのでしょうか。。。
（例：プログラミング令和5年秋問2（3）
https://www.ap-siken.com/kakomon/05_aki/pm03.html）
表際の件について
午後問のプログラミングに出てくるオーダ記法を求めさせる問題が解説を読んでも理解できません。
1.解き方のコツはありますでしょうか。
2.掛ける労力に対してリターンが少ないので基本的なオーダ記法以外は捨て問とした方が良いのでしょうか。。。
（例：プログラミング令和5年秋問2（3）
https://www.ap-siken.com/kakomon/05_aki/pm03.html）
2025.06.13 23:00
jjon-comさん(No.2)
★AP プラチナマイスター
応用情報 令和5年 秋期 午後 問3
https://www.ap-siken.com/kakomon/05_aki/pm03.html
最悪の場合の探索回数がもっとも大きくなる2分探索木は
https://www.ap-siken.com/kakomon/05_aki/img/pm03_8.png
片方の枝だけが伸びて2分木に思えないけれど、ちゃんと2分木の定義を満たしています。
この図から次のことが読み取れます。
要素数n＝4のとき 最大探索回数は 4回。
要素数n＝3のとき 最大探索回数は 3回。
要素数n＝2のとき 最大探索回数は 2回。
つまり 最大探索回数は「ｎに比例する」。
これをオーダ（ビッグオー記法）で Ｏ(ｎ) と書きます。
最悪の場合の探索回数がもっとも少なくなる2分探索木は
https://www.ap-siken.com/kakomon/05_aki/img/pm03_9.png
この図から次のことが読み取れます。
要素数n＝15 のとき 最大探索回数は 4回。（この4は ２のx乗＝16 となる場合の x）
要素数n＝ 7 のとき 最大探索回数は 3回。（この3は ２のx乗＝8 となる場合の x）
要素数n＝ 3 のとき 最大探索回数は 2回。（この2は ２のx乗＝4 となる場合の x）
そして数学では、
「２のx乗＝ｎ」という指数の関係があるときの x を表すのに
「x＝log2 ｎ」という対数表記を使用します。
つまり最大探索回数は「log2 ｎ に比例する」
これをオーダ（ビッグオー記法）で Ｏ(log ｎ) と書きます。
https://www.ap-siken.com/kakomon/05_aki/pm03.html
最悪の場合の探索回数がもっとも大きくなる2分探索木は
葉を除く全てのノードについて左右のどちらかにだけ子ノードが存在する場合
解説に添えられている具体例はこちら。https://www.ap-siken.com/kakomon/05_aki/img/pm03_8.png
片方の枝だけが伸びて2分木に思えないけれど、ちゃんと2分木の定義を満たしています。
この図から次のことが読み取れます。
要素数n＝4のとき 最大探索回数は 4回。
要素数n＝3のとき 最大探索回数は 3回。
要素数n＝2のとき 最大探索回数は 2回。
つまり 最大探索回数は「ｎに比例する」。
これをオーダ（ビッグオー記法）で Ｏ(ｎ) と書きます。
最悪の場合の探索回数がもっとも少なくなる2分探索木は
葉を除く全てのノードに左右両方の子ノードが存在し，また，全ての葉の深さが等しい完全な2分探索木
なるべく左右両方の子ノードが存在するように配置して，高さができるだけ低くなるように構成した木であることが望ましい。このような木のことを平衡2分探索木という。
解説に添えられている具体例はこちら。なるべく左右両方の子ノードが存在するように配置して，高さができるだけ低くなるように構成した木であることが望ましい。このような木のことを平衡2分探索木という。
https://www.ap-siken.com/kakomon/05_aki/img/pm03_9.png
この図から次のことが読み取れます。
要素数n＝15 のとき 最大探索回数は 4回。（この4は ２のx乗＝16 となる場合の x）
要素数n＝ 7 のとき 最大探索回数は 3回。（この3は ２のx乗＝8 となる場合の x）
要素数n＝ 3 のとき 最大探索回数は 2回。（この2は ２のx乗＝4 となる場合の x）
そして数学では、
「２のx乗＝ｎ」という指数の関係があるときの x を表すのに
「x＝log2 ｎ」という対数表記を使用します。
つまり最大探索回数は「log2 ｎ に比例する」
これをオーダ（ビッグオー記法）で Ｏ(log ｎ) と書きます。
2025.06.14 00:51
jjon-comさん(No.3)
★AP プラチナマイスター
オーダを理解するための要点は、
・Ｎに小さな値を想定しないこと。要素数Ｎが 万、億、兆 と増加していったときに計算量（実行時間）が何に比例して増加していくかをイメージすること。
・定数・係数を無視すること。万、億、兆 と増加するＮと比べて影響が少ないので。
具体例をいくつか挙げます。
No.2で私は
と書きましたが、この基本情報ドットコムの解説では、4回目の探索でも失敗する例も加えて 5回としています。私がこの＋1を無視したのは、Ｎの増加に比べて誤差でしかないから。ちなみにこの定数が＋100や＋10000であっても無視します。
この基本情報ドットコムの解説では正しく ｎー１ と書いているのに、No.2で私は 15と16、7と8、3と4 を同一視しました。このー1を無視したのはオーダにとって誤差でしかないから。
No.2で私は
と書きました。
探索回数では「log2 ｎ に比例する」（２のx乗＝ｎ の x に比例する）と 2 が書かれているのに、
オーダ表記では「log ｎ」（何かのx乗＝ｎ の x に比例する）と 2 が書かれていません。
これも係数を無視したから。２の乗数だろうが、10の乗数だろうが、Ｎが巨大になっていくときの計算量の増加のカーブの度合いを問題にしているということです。
最後にもう一例。
あるプログラムの実行時間が Ｎの2乗 ＋ Ｎ で表されるなら、そのオーダは Ｏ(Ｎの2乗) です。Ｎの2乗 に比べて Ｎ の変化が小さいので無視します。
・Ｎに小さな値を想定しないこと。要素数Ｎが 万、億、兆 と増加していったときに計算量（実行時間）が何に比例して増加していくかをイメージすること。
・定数・係数を無視すること。万、億、兆 と増加するＮと比べて影響が少ないので。
具体例をいくつか挙げます。
No.2で私は
> 要素数n＝4のとき 最大探索回数は 4回。
と書きましたが、この基本情報ドットコムの解説では、4回目の探索でも失敗する例も加えて 5回としています。私がこの＋1を無視したのは、Ｎの増加に比べて誤差でしかないから。ちなみにこの定数が＋100や＋10000であっても無視します。
この基本情報ドットコムの解説では正しく ｎー１ と書いているのに、No.2で私は 15と16、7と8、3と4 を同一視しました。このー1を無視したのはオーダにとって誤差でしかないから。
No.2で私は
> つまり最大探索回数は「log2 ｎ に比例する」
> これをオーダ（ビッグオー記法）で Ｏ(log ｎ) と書きます。
と書きました。
探索回数では「log2 ｎ に比例する」（２のx乗＝ｎ の x に比例する）と 2 が書かれているのに、
オーダ表記では「log ｎ」（何かのx乗＝ｎ の x に比例する）と 2 が書かれていません。
これも係数を無視したから。２の乗数だろうが、10の乗数だろうが、Ｎが巨大になっていくときの計算量の増加のカーブの度合いを問題にしているということです。
最後にもう一例。
あるプログラムの実行時間が Ｎの2乗 ＋ Ｎ で表されるなら、そのオーダは Ｏ(Ｎの2乗) です。Ｎの2乗 に比べて Ｎ の変化が小さいので無視します。
2025.06.14 00:52
小たけさん(No.4)
個人的には代表的なものをいくつか暗記しておくだけで良いと思います。
・二分探索法 O(logn)
・線形探索法 O(n)
・挿入ソート O(n^2)
・順列全探索 O(n!))
・二分探索法 O(logn)
・線形探索法 O(n)
・挿入ソート O(n^2)
・順列全探索 O(n!))
2025.06.16 13:04
jjon-comさん(No.5)
★AP プラチナマイスター
「暗記する」と「理解する」を比べて、後者のほうを
と捉えるのか、そうでないのか、の違いということになるのでしょうか。
私は、小学校で習った 台形の面積 や 円の面積 を公式で覚えていません。
「台形の面積は？」と問われたら、脳裏にはいまだに
台形を2つ互い違いに並べたイラストが思い浮かびますし、
「円の面積は？」と問われたら、脳裏にはいまだに
細切れになったピザを並べて台形になったイラストが思い浮かびます。
ですから、なぜその公式になるのかを説明できます。
私は、線形探索、二分探索、挿入ソート、と問われたら、
その動きがイラストで思い浮かぶような勉強をしました。
ですから、基本的には
ですが、整列済みの配列に対してはそうではないことを説明できます。
このようなイメージで理解した者にとっては、オーダは「易しい問題」です。
アルゴリズムのイメージそのものがオーダですから。
> 掛ける労力に対してリターンが少ない
と捉えるのか、そうでないのか、の違いということになるのでしょうか。
私は、小学校で習った 台形の面積 や 円の面積 を公式で覚えていません。
「台形の面積は？」と問われたら、脳裏にはいまだに
台形を2つ互い違いに並べたイラストが思い浮かびますし、
「円の面積は？」と問われたら、脳裏にはいまだに
細切れになったピザを並べて台形になったイラストが思い浮かびます。
ですから、なぜその公式になるのかを説明できます。
私は、線形探索、二分探索、挿入ソート、と問われたら、
その動きがイラストで思い浮かぶような勉強をしました。
ですから、基本的には
> ・挿入ソート O(n^2)
ですが、整列済みの配列に対してはそうではないことを説明できます。
このようなイメージで理解した者にとっては、オーダは「易しい問題」です。
アルゴリズムのイメージそのものがオーダですから。
2025.06.16 17:50