• ベストアンサー

決定木を用いて、ソーティングアルゴリズムの計算量の限界を説明するにはど

決定木を用いて、ソーティングアルゴリズムの計算量の限界を説明するにはどうすればいいですか？ 教えてください。

質問者が選んだベストアンサー

  • ベストアンサー
  • Tacosan
  • ベストアンサー率23% (3656/15482)
回答No.1

決定木の高さがどのくらいになるかをいう.

  1. カテゴリ
  2. [技術者向] コンピューター
  3. プログラミング・開発
  4. その他（プログラミング・開発）

関連するQ&A

  • アルゴリズムの計算量

    アルゴリズムの計算量とはどういう意味なんでしょうか？またそれを知るとどんな意義がありますか？ 教えてください。

  • C4.5について　決定木

    現在，決定木の勉強をしていてます． そこでC4.5というアルゴリズムがあることを知りました． しかし，マニュアルが英語であらわされていて詳しい使い方がよくわかりません． 誰か使い方を知っている方は教えてもらえないでしょうか． よろしくお願いします．

  • 2進アルゴリズムの時間計算量

    ベキ乗計算を2進アルゴリズムで解いた場合の時間計算量を求める方法を教えてください。 x^nの時の時間計算量でn=2,3以外の時でn=2p,2p+1の時で場合わけして(pは整数)数学的帰納法で解いてあるのは見た事はあるのですが、どこからその仮定を持ってきたのか見当がつきません。 どうかお願いします。 n>3のときの時間計算量kは　k<=(2*log(n))-1 となっていました。

  • アルゴリズムの2-3-4木

    アルゴリズムの2-3-4木 アルゴリズムの平衡木の一種である2-3-4木を使い、テキストファイルに書かれている文中の英単語1文字1文字を挿入し（同じ単語は1度だけ）、全ての単語の配置（パラグラフ、行数）を表示するというプログラムを考えているのですが、どのように組めばいいのかがわかりません。 例えばテキストファイルの文中に、studyという単語が1つ目のパラグラフの2行目、2つ目のパラグラフの4行目にあれば、 study (1,2) (2,4) と表示するプログラムです。2-3-4木ではどのようにデータを格納していくかはわかったのですが、データの挿入やノードの分割などをプログラムではどのように書けばいいのでしょうか。 どなたかご教授お願いいたします。

  • アルゴリズムの説明について

    アルゴリズムを新人に教育するようにいわれ困っています。 下記の様な説明でよいか判断が付きません。又、ＤＢの更新はフローチャート上表現できないのでどうしたらよいか悩んでいます。 宜しくお願いします。 アルゴリズムとはある問題を解決する手順。 プログラムを作成するときのロジックを構築しますが、 それらの処理手順すべてがアルゴリズムというわけです。 プログラムはアルゴリズムを表記するということになります。

  • 計算量について

    プログラムの計算量について質問です。計算量には時間計算量と空間計算量がありますが、そのうち空間計算量の概念がいまいち分かりません。アルゴリズムが必要とする記憶容量といっても漠然としててどのように求めたらいいのか分かりません。 例えばプログラムの基本構成が for(n回){ for(n回){ 処理 } } のようだったら時間計算量がO(n^2)というのはわかるんですが、この場合の空間計算量はどのようになりますか?

  • ハミルトン閉路の計算量についての質問です。

    ハミルトン閉路の計算量についての質問です。 教科書で、ハミルトン閉路の計算量が２のｎ乗となっていたのですが、 なぜ、その計算量なのか、ということがよくわかりません。 自分的には、ハミルトン閉路の最良アルゴリズムが、全数検索アルゴリズムであるので、 節点の順列すべてに対してハミルトン閉路か否かを調べる必要があるから、というような 理由を考えたのですが、 具体的になぜ２のｎ乗なのかがいまいちわかりません。 分かる方おられましたらお教え下さい。 お願いし致します。

  • 優先順位を決定するアルゴリズム

    優先順位を決定するアルゴリズムがありましたら ご教授下さい． やりたい事は，以下の通りです． ・A,Bの二人がいる． ・二人はそれぞれというパラメータを持つ． ・各自パラメータに優先順位をつけている． ・二人にとってのパラメータの優先順位を決定する 例）A,Bがそれぞれ，a,b,cというパラメータを持つ． 各自パラメータに優先順位をつけている． A a:1 b:2 c:3 B a:2 b:2 c:1 この時，二人にとってのパラメータの優先順位を決定する．私は，以下の方法を考えました． 1.二人のパラメータの優先順位を足して 合計値を計算する． 2.値が同じ場合は，値の分散値が低い方が，優先順位が低いとする a：1+2 = 3 b：2+2 = 4 c :3+1 = 4 bの分散値の二乗：(2-2)の二乗　＋　(2-2)の二乗 cの分散値の二乗：(3-1)の二乗　＋　(2-1)の二乗 よって，bとcでは，bの方が優先順位が低いとする この他にも，優先順位を決定するアルゴリズムに関して，他の方法や，既存研究等がありましたらご教授下さい．

  • 決定木学習について

    研究で制御端の状態判断を行うのですが、その中で決定木学習を行ってみようと思いました。 いろいろ文献などを探しているのですが、なかなかアルゴニズム等を詳しく記したものが見つかりません。 決定木学習についての知識、文献、論文など知っていたら教えてください。。 特にアルゴニズムを。。

  • 計算量(PやNP)について

    ネット上で計算量理論に関する説明を読んでいますが、いまいち理解ができません。 例えば、木の形で表せれる問題で、一つのノードに対する子がN個(定数)あり、深さX(未知、変数)に答えがある場合、計算量は N^X(NのX乗) になると思います。 N^Xは計算量のクラス(NP困難やNP完全等)でいうと何に属するのでしょうか？

注目のQ&A

カテゴリ

専門家に質問してみよう

職業から探して質問する

あなたにピッタリな商品が見つかる！ OKWAVEセレクト

質問する