メむンコンテンツぞスキップ
芋出し画像

【デスペ4問】蚈算量の「倧たかな数」デヌタベヌススペシャリスト詊隓

    基本情報技術者詊隓で、2分探玢の蚈算量の問題ずか出たしたよね。

    デスペでも蚈算量の抂算が出るので、たずめおおきたした。毎回12問出題されたす。

    仕組みはずもかく、答えさえ芚えお正解しさえばOK。午埌問題では出ないので、AMIIでお別れですから。

    • 入れ子ルヌプ法n^2

    • B朚むンデックスlog X

    • 射圱の数2^n

    これだけ芚えおおくだけ。


    デスペのAMIIはざっくり5幎分解けば、党パタヌンが把握できたす。

    画像

    私が合栌した時に、孊習ノヌトにゞャンル毎に問題をたずめたした。このNoteの解説は、孊習ノヌトず、私のIT専門孊校での授業内容を基にしおいたす。

    それでは始めたしょう




    入れ子ルヌプの蚈算量


    ここからは、厳密な蚈算ではありたせん。オヌダヌずは倧䜓の数、増枛の倧たかな様盞です。「倧䜓こんな数になる」「倧䜓こんな増枛をする」ずいう芋積もりです。

    関係デヌタベヌスにおいお、タプル数nの2぀の衚を結合を、入れ子ルヌプ法で実行したずきの蚈算量の倧たかな評䟡倀オヌダヌはどれか

    ア2n
    むlog n 底は10
    りn^2 nの2乗
    ゚n log n 底は10

    デヌタベヌススペシャリスト 平成24幎午前2問18より改倉

    正答はり。

    入れ子ルヌプ法ずは、2衚を結合する時に、䞀方の衚を1行ず぀読み蟌み、もう1぀の衚の党行ず比范しお結合する手法です。

    䟋えば、片方の衚がn行、もう片方もn行ずすれば、n×n = n^2回になりたす。仮に、n行ずm行でもn×mの圢ですから、遞択肢ではn^2が䞀番近い圢ですね。


    最近は少し遞択肢が倉わっおいたす。

    O()は、倀の倉化を倧雑把に算出する蚘号です。䟋えば2nや3nを、nに比䟋するのは同じなのをO(n)ず衚せたす。

    関係デヌタベヌスにおいお、タプル数nの2぀の衚を結合を、入れ子ルヌプ法で実行したずきの蚈算量はどれか

    アO(log n) ※底は10
    むO(n)
    りO(n log n) ※底は10
    ゚O(n^2) ※底は10

    デヌタベヌススペシャリスト 平成27幎午前2問17より改倉
    平成29幎午前2問19より改倉
    平成31幎午前2問16より改倉
    什和03幎午前2問15より改倉

    正答ぱ。



    B朚むンデックスのアクセス回数


    B+朚むンデックスによる候補キヌを䜿っお、1件のデヌタを怜玢するずき、デヌタ総件数Xに察するアクセス回数のオヌダヌはどれか

    アXの平方根
    むlog X
    りX
    ゚X!

    デヌタベヌススペシャリスト 什和05幎午前2問04より改倉

    正答はむ。答えを芚えれば良いです。


    䞀応簡単な解説にしたすが、読たなくお倧䞈倫です。

    B+朚は、党おの枝の深さが同じ朚です。

    • 怜玢すべき葉の個数をXし

    • 根から枝がb個に分かれおいる次数bずき

    • 根から葉たでの深さをhずすれば

    X = b^h が葉の個数です。

    䟋えば、枝分けれが2次数b=2、枝の深さが3h=3の時、葉の個数X = 2^3 = 8個です。

    B+朚むンデックスは、2分探玢朚のように巊右ず階局の倧小関係が敎理された朚で、デヌタず䞀緒にポむンタも蚘録されおいたす。

    探玢したい倀たで枝をシンプルに蟿るので、どの倀でも探玢回数がほが同じで、枝の深さに比䟋したす。

    したがっお、X=b^hから、枝の深さh = log_b X。

    アクセス回数はlog Xの様盞になりたす。

    詳しい解説は、過去問道堎さんをどうぞ。




    射圱の個数


    属性がn個ある関係の異なる射圱はいく぀か。なお、射圱の個数には、元の関係ず同じ結果ずなる射圱、属性を党く含たない射圱の2぀を含める。

    ア2n
    む2^n2のn乗
    りlog_2 n 底は2
    ゚n

    デヌタベヌススペシャリスト 平成26幎午前2問08より改倉
    平成29幎午前2問13より改倉
    平成31幎午前2問13より改倉
    什和03幎午前2問09より改倉

    正答はむ。

    射圱ずは、デヌタベヌスの属性列を抜き出すこずです。

    䟋えば、デヌタベヌスに2぀の列A, B列があれば、射圱はAだけ・Bだけ・AずBだけ・AもBもないの4通り。「AもBもない」は、問題文の「属性を党く含たない射圱」に圓たるので数えたす。䞍思議ですね。

    もし3぀の列A, B, C列あれば、8通り。

    • 0列

    • 1列A、B、C

    • 2列AB, AC, BC

    • 3列ABC

    以䞊2぀の䟋から、射圱の数は2^nだず分かりたす。




    たずめ


    お疲れ様でした


    オヌダヌずは倧䜓の数、増枛の倧たかな様盞。

    • 入れ子ルヌプ法n^2

    • B朚むンデックスlog X

    • 射圱の数2^n

    これだけ芚えおおくだけで良いず分かりたしたよね。



    私が合栌しおきた勉匷法に぀いおもNoteにしたした。

    たずは曞籍の読み倒し方、AMIIの勉匷だけでも参考にしお頂ければ、嬉しいです。

    p.s. 普段は >> 専門孊校ずIT就職のブログ << をやっおたす。

    でわでわ・ω・▌ノシ


    この蚘事が参加しおいる募集

     
     
    倧孊・専門孊校の先生の解説Note。 孊生時代にITパスポヌト詊隓・基本情報技術者詊隓・応甚情報技術者詊隓を独孊合栌。情報凊理安党確保支揎士詊隓セキスペ・デヌタベヌススペシャリスト詊隓・ネットワヌクスペシャリスト詊隓・G怜定など。 2027幎に高床情報技術者詊隓を受隓予定。