ベストアンサー 決定木を用いて、ソーティングアルゴリズムの計算量の限界を説明するにはど 2010/08/02 22:40 決定木を用いて、ソーティングアルゴリズムの計算量の限界を説明するにはどうすればいいですか? 教えてください。 みんなの回答 (1) 専門家の回答 質問者が選んだベストアンサー ベストアンサー Tacosan ベストアンサー率23% (3656/15482) 2010/08/02 23:39 回答No.1 決定木の高さがどのくらいになるかをいう. 通報する ありがとう 0 カテゴリ [技術者向] コンピュータープログラミング・開発その他(プログラミング・開発) 関連する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木ではどのようにデータを格納していくかはわかったのですが、データの挿入やノードの分割などをプログラムではどのように書けばいいのでしょうか。 どなたかご教授お願いいたします。 アルゴリズムの説明について アルゴリズムを新人に教育するようにいわれ困っています。 下記の様な説明でよいか判断が付きません。又、DBの更新はフローチャート上表現できないのでどうしたらよいか悩んでいます。 宜しくお願いします。 アルゴリズムとはある問題を解決する手順。 プログラムを作成するときのロジックを構築しますが、 それらの処理手順すべてがアルゴリズムというわけです。 プログラムはアルゴリズムを表記するということになります。 計算量について プログラムの計算量について質問です。計算量には時間計算量と空間計算量がありますが、そのうち空間計算量の概念がいまいち分かりません。アルゴリズムが必要とする記憶容量といっても漠然としててどのように求めたらいいのか分かりません。 例えばプログラムの基本構成が for(n回){ for(n回){ 処理 } } のようだったら時間計算量がO(n^2)というのはわかるんですが、この場合の空間計算量はどのようになりますか? ハミルトン閉路の計算量についての質問です。 ハミルトン閉路の計算量についての質問です。 教科書で、ハミルトン閉路の計算量が2のn乗となっていたのですが、 なぜ、その計算量なのか、ということがよくわかりません。 自分的には、ハミルトン閉路の最良アルゴリズムが、全数検索アルゴリズムであるので、 節点の順列すべてに対してハミルトン閉路か否かを調べる必要があるから、というような 理由を考えたのですが、 具体的になぜ2のn乗なのかがいまいちわかりません。 分かる方おられましたらお教え下さい。 お願いし致します。 優先順位を決定するアルゴリズム 優先順位を決定するアルゴリズムがありましたら ご教授下さい. やりたい事は,以下の通りです. ・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完全等)でいうと何に属するのでしょうか? 線量の計算アルゴリズムの乗っているサイトや本 計算アルゴリズムのAAA,PBC,Acuros XB法について詳しく乗っている本やサイトをしりませんか?できれば、アルゴリズムの進化なども載っていると嬉しいです 計算を含んだ説明を教えてください。 0.1n水酸化ナトリウムの調整 量り取った水酸化ナトリウム:2.00g 調整量:500ml どうして上記を量り取ったのか説明しなさい。 ※計算式等を用いて説明しなさい。 の答えをおしえていただきたいです。 時間計算量とオーダーに関する問題がわかりません 1.サイズnの入力に対する、あるアルゴリズムの時間計算量f(n)が、F(n)=2^(2n)であるとする。 このとき、f(n)がO(2^n)でないことを示しなさい。 2.サイズnの入力に対する、あるアルゴリズムの時間計算量f(n)が、f(n)=c^(2n)であるとする。ただし、CはC>1の実数とする。このとき、F(n)がO(c^n)であるといえるか否かを示しなさい。 この二つの問題ですが、全然分かりません。 導出方法を教えてください。お願いします。 h-indexを計算するアルゴリズム 自分の研究業績を評価する一つの方法として h-indexというものがありますが、 これをマクロを使わずにexcelで簡便に計算できるアルゴリズムがあれば教えてください。 二分探索木のheight(高さ?)を見つけるアルゴリズム Binary Search Tree(=二分探索木)のheight(高さ?)を見つけるメソッドを作りたいのですが、 そのアルゴリズムが頭にうまく浮かびません。 まず思いついたのは一つ一つのNode(=ノード)をそれぞれのLeaf(=リーフ、葉?)まで辿っていって それらのheightを全部記憶させておいて後で比較するという…最も原始的な方法です。 しかし、Treeの大きさも未知なので用意する変数の数も未知になって どう考えても不適当でしょう(当たり前か(^^ゞ)。 Recursion(=再帰)を使えばいいのでしょうか? そうだとしてもどうすればいいのか…。 アルゴリズムがパッと浮かぶ方、どうか教えて下さい。 素数判定アルゴリズム内の剰余計算 今勉強している任意倍長精度整数の素数を判定するアルゴリズム内で x^q mod n という計算をするところがあるのですが、 正確に計算しようとすると計算量が膨れ上がってしまって 高速にできなくて困っています。 参考にしている文献に "x^q mod nの計算ではx^q mod nを正確に求める必要は無く、 x^q ≡ x^q' (mod n)となる x^q'でよい"という記述があるのですが どういう意味なのかよくわかりません。 どなたか教えていただけないでしょうか? アルゴリズム(2分探索木)の問題について 2分探索木のアルゴリズムに関する問題について質問させていただきます。 [問題] 集合Sに対する2文探索木とは、ラベルつきの2分木で、 その頂点vにはSのある要素l(v)がラベルとしてつけられている。 l(v)は次の性質を満たす。 1.vの左部分木の頂点uに対して l(u) < l(v) 2.vの右部分木の頂点uに対して l(u) > l(v) 3.Sの任意の要素aに対して l(v) = a となる頂点vはちょうどひとつある。 図はキーワード集合{begin,else,end,if,then}をあらわす2分探索木の例である。 いま、集合Sを表す2分探索木と要素aが与えられているときa∈Sならば"はい"、 そうでなければ"いいえ"を出力するアルゴリズムを考える。 このアルゴリズムは、木の根rについて一回だけ再帰手続きSEARCH(a,r)を呼び出せばよい。 ただし、SEARCH(a,v)はvを根とする部分木中に要素aが含まれているかを判定する。 含まれているときに値"はい"を、そうでなければ値"いいえ"を返す。 ・アルゴリズム procedure SEARCH(a,v): if a = l(v) then return "はい" else if a < l(v) then if vが左の子wを持つ then return SEARCH( ア ) else return "いいえ" else イ 以下の問題に答えよ。 (1) 上のアルゴリズムのア,イを埋めよ。 (2) 上のアルゴリズムを参考にして、集合Sからのデータの削除DELETE(a,S)を考える。 削除すべき要素aが頂点vのラベルであったとする。そのとき次の3つの場合について、行うべき操作を記述せよ。 (i) 頂点vが葉である (ii) 頂点vの子が1個ある (iii) 頂点vの子が2個ある 以上です。 設問(1)は解けました。 答えは ア: a,w イ: a > l(v) then if vが右の子wを持つ then return SEARCH(a,w) else return "いいえ" になるのではないかと思います。 設問(2)についてなのですが、それぞれの場合について、どのような操作をすればよいのかは、 参考書などを読んで理解したのですが、どのように記述したらよいかがわかりません。 長文になってしまい申し訳ないのですが、回答よろしくお願いいたします。 計算量 記憶計算量と時間計算量の求め方がいまいちよくわかりません。どなたか教えてください。 木構造(位相構造)を比較するアルゴリズムって? 木構造(位相構造)を2つ用意し、根からたどって比較してゆき、 差分をとるようなプログラムを書こうと思っています。 しかしアルゴリズムがまったくわからないので質問させていただきます。 子ノードの順番が異なる場合も同じものと見なすような条件で、 末端にノードが追加された程度の差異がわかればよいです。 (鏡に映した構造や、子ノードがABCという順だったのを、ACBにしたような構造は同じものと見なしたいということです。) このようなアルゴリズムというのはあるのでしょうか? 時間計算量、空間計算量とは何でしょうか? 時間計算量、空間計算量とは何でしょうか? 大学の課題ででた問題ですが全く分からないのでお力を貸していただきたいです。 時間計算量、空間計算量とは何かを調べまた、バブルソートの時間計算量と空間計算量を求めよという問題が出たのですがさっぱり分かりませんでした・・・ どこか分かりやすいサイトなどに誘導してもらえるとうれしいです。 注目のQ&A 「前置詞」が入った曲といえば? 緊急性のない救急車の利用は罪になるの? 助手席で寝ると怒る運転手 世界がEV車に全部切り替えてしまうなら ハズキルーペのCMって…。 全て黒の5色ペンが、欲しいです 長距離だったりしても 老人ホームが自分の住所になるのか? 彼氏と付き合って2日目で別れを告げられショックです 店長のチクチク言葉の対処法 カテゴリ [技術者向] コンピューター プログラミング・開発 Microsoft ASPC・C++・C#CGIJavaJavaScriptPerlPHPVisual BasicHTMLXMLCSSFlashAJAXRubySwiftPythonパフォーマンス・チューニングオープンソース開発SEOスマートフォンアプリ開発その他(プログラミング・開発) カテゴリ一覧を見る あなたにピッタリな商品が見つかる! OKWAVE セレクト コスメ化粧品 化粧水・クレンジングなど 健康食品・サプリ コンブチャなど バス用品 入浴剤・アミノ酸シャンプーなど スマホアプリ マッチングアプリなど ヘアケア 白髪染めヘアカラーなど