Serviceを読んで理解し、同意したものとみなします。スタック・オーバーフローはプログラマーとプログラミングに熱心な人のためのQ&Aサイトです。519件1二分探索木の平均の計算量を示す方法について下記画像の結果よりすべてのnについてT(n)<4logn+1が示せたことになり、木の平均深さがO(logn)であることがわかるそうです。下記画像の二分探索木の平均の計算量を示す方法について5点不明な箇所がございます。alogn+bを仮定する理由について上記のように仮定する理由は最終的に計算量はaとbを除いて考えれるからでしょうか。(2)n=1のときはb=1とすれば成立する上記の記載についての意図が理解できません。(3)画像下の式で<=としている箇所についてです。<=としているのでしょうか。(4)式の2行目と3行目のシグマの右側ailogi+iをシグマの左側2a/k^2に変化する意図が理解できません。(途中式が浮かびません)(5)ここで1~k/2とk/2+1~k-1に分けるの式がほぼ全く理解できません。疑問点をうまくまとめれませんでしたが、ご解説いただければ幸いです。票2「解を仮定してその正しさを帰納法で示す方法をとる」という説明が理解できない、より具体的には『帰納法』が何なのかを十分に理解していらっしゃらないのだと思われます。求められる』という公式を例にして、帰納法による証明がどんなものか示します。(自然数というのは、0より大きな整数の事。nがXの時に正しければ、nがX+1の時にも正しいの2つを示せば足ります。(a)で、nが一番小さい自然数である1の時に成り立つことが示され、(b)で、nが1の時に正しいのだから、nが2の時も正しいさらに、(b)で、nが2の時に正しいのだから、nが3の時も正しい...というように(b)を繰り返し使っていくと、すべての自然数で成立することが示せます。・値の変更("1増やす")を繰り返す事で、公式が適用できる範囲が一般化できるをもって公式の証明をする方式を帰納法と言います。===「2分木探索」について考えてみましょう。2分木は「左の子の値<親の値<右の子の値」が成り立つような値をノードが持つ木構造です。2分木探索は、2分木を使った検索で、根のノードから初めて、探す値と一致するまでノードを辿っていきます。値が一致するノードが見つかるまでに値の比較をした回数が計算量になります。log2(N)ほどになります。log2は、2を底とする対数。2分木の高さは、計算量の上限(最悪値)ですから、左右均等な2分木の場合は計算量の上限はO(log(N))といえます。左右均等な場合が、計算量の上限が最小です。計算量の上限が大きいのは、一方にだけ枝が伸びた2分木(一直線状の木)で、計算量の上限はNです。alogn+bという式です。a*log(n)の部分が左右均等な木の場合の上限値、bが一方にだけ枝が伸びた木の場合の上限値で、両方を加えたものは、どちらが支配的でも実際の上限より小さくならない事を表しています。aやbといった値は、帰納法による証明を始める時点では未定です。<(2)n=1のときはb=1とすれば成立する>例えば、2分木が1つのノードだけの場合、計算量(T(n))は1(比較するノードは1個だけ)、ノードの個数(n)は1、一方に枝が伸びた木の場合の上限値(b)は1。alogn+bがn=1の時に成立する。(その時のbは1)<(3)画像下の式で<=としている箇所についてです。計算量の上限(alogn+b)が成り立つ。(2)のように等号が成り立つ場合もある。"<"ではなく"<="としている。==このような道筋で考えていくと理解できるのではないでしょうか。個の銅バッジご解説ありがとうございます。ご指摘どおり帰納法が何なのかを十分に理解しておりませんでした。作成しそれへのリンクを貼ります。リンクhttps://drive.google.com/open?id=1QHhrCu4-2Sn48rYnyawEruyxINansKCg正直に申し上げるとこの書籍を読み続ける前に高校の数学の復習(今回は数列分野)を最低でも章末問題を完答できる程度に勉強をなさったほうがよりスムーズにこの書籍を読み込めるようになると思います。(3)および(4)について:でミスがあったので修正しました。16:43丁寧な解説ありがとうございます。本書を読む中で高校の数学が理解できていないことに気づきました。数学Bの教科書を購入し直しました。1~k/2とk/2+1~k-1の途中式の変形も理解できなかったので数学を復習し直し再度トライしようと考えています。12:21土台さえしっかりしていればその上にいろいろ築くのは楽になります。遠回りのようですがこれが一番の近道となりますので頑張ってください。1〜k/2とk/2+1〜k-1に分ける考え方はその手法がわかったとしても変形に手間取るかもしれません(難関大理系入試レベル?)。分からないことがあったらまた質問してくださいね。12:38ありがとうございます。|回答スタック・オーバーフローに参加してくれて、ありがとうございます!質問の回答を共有してください。回答を説明し、自分の検討結果も共有してください。意見を述べること(意見を述べるなら、参照リソース、自分の経験で意見をサポートしてください)さらにサポートが必要な場合このヘルプを参考してください。“回答を投稿”をクリックすることで利用規約、プライバシーポリシー、及びクッキーポリシーに同意したものとみなされます。タグが付いた他の質問を参照するか、自分で質問をする。App.configのデータ取得について5グラフ理論について、三次元空間における位置関係の情報をinvariantに保持する表現を計算したい0分割統治法を利用した数式についてです。1数式の変形の過程について132ビット整数がでたらめな順に入っているファイルに入っていない32ビット整数を一つ見つけてください。質問のフィードこのRSSフィードを購読するには、このURLをコピーしてRSSリーダーに貼り付けてください。