探索のアルゴリズムと計算量 - クラスライブラリ基礎
今回も「明解 Javaによるアルゴリズムとデータ構造」を参照します。 この本に掲載されているサンプルプログラムは著者の後援会のサイトからダウンロードできますが、 文字コードが Shift JIS なため、UTF-8 に変換したものを以下に置いておきます。 第3章 サンプルプログラム 多くの要素を持つデータの中から、 条件にあう要素を探し出すことを探索(searching)と言います。 「明解 Javaによるアルゴリズムとデータ構造」 pp.74-75 線形探索 ランダムに並んだデータから、一つずつ取り出して探していくのが線形探索です。 配列を先頭から調べていくのが典型例で、すでに体験済みの手法でしょう。 「明解 Javaによるアルゴリズムとデータ構造」 pp.76-81 2分探索 2分探索は、ソートされたデータから要素を探すアルゴリズムです。 「明解 Javaによるアルゴリズムとデータ構造
計算量を具体的に見てみる 2009-01-06 - きしだのはてな
アルゴリズムの話では、計算量の解析がかかせません。 計算量はオーダー記法で表されますが、これは、データの入力量に対してどのくらい時間がかかるかをあらわしたものです。 こういった話はどのアルゴリズムの本にも載ってるはずですが、具体的にどのようなプログラムを書くとそのオーダーになるかという記述はあまりありません。 ということで、やってみました。 計算時間表示のための共通処理を行うクラスは、一番最後に書いてます。 O(1) 計算時間がO(1)のアルゴリズムは、処理が入力の量によらない場合です。 配列の要素のアクセスや、ハッシュテーブルによるデータ検索、連結リストへの追加削除などがこれにあたります。 コードには入力量でのループが含まれません。 public class O1 extends ViewCompFrame{ @Override void compute(int n) { proc();
プログラマならみんな知ってるよね!データ構造と計算量について | SONICMOOV LAB
9日目らくさんの記事を読んで計算量を意識することがいかに重要かということを学んだ、ムックです。 というわけで、ソニックムーブ Advent Calendar 2013 14日目はプログラマならみんな知っているであろう、データ構造と計算量について改めて調べてみました。 まず、データ構造とは データ構造（データこうぞう、英: data structure）は、計算機科学において、 データの集まりをコンピュータの中で効果的に扱うため、一定の形式に系統立てて格納するときの形式のことである。 — wikipedia抜粋 データ構造には、いくもの種類があるが良し悪しがなくどういったデータをどう処理するかによって効率が大きく変わっていきます。 データ構造の主な種類 配列(Array) プログラムをかじったことがある人は誰しも知っているであろうArray。 同じサイズの要素を並べただけのデータ構造です。
アルゴリズムと計算量
金庫破りと計算量膨張 n 桁の番号をもつ暗証ロックがあるとします。 2 桁であれば 00 〜 99 の 100 個の正解があるわけで、 0 番から順に入力していく解き方では、 最悪の場合は 100 手目に開きます。 99 が正解とは限らないので、平均的にはこれより早く解き終わります。 0 であるときの確率は 1/100 で、このときの手数は 1 手です。 1 であるときの確率は 1/100 で、このときの手数は 2 手です。 2 であるときの確率は 1/100 で、このときの手数は 3 手です。 3 であるときの確率は 1/100 で、このときの手数は 4 手です。 : 99 であるときの確率は 1/100 で、このときの手数は 100 手です。 つまり、平均手数は により、100 手目の約半分です。 ここでいう解き方をアルゴリズムといい、 問題を解くための手数 (てかず) のことを計算
ランダウの記号 - Wikipedia
スターリングの公式はランダウの記号を用いてと書くこともできる。 ランダウの記号（ランダウのきごう、英: Landau symbol）は、主に関数の極限における漸近的な挙動を比較するときに用いられる記法である。 ランダウの漸近記法 (asymptotic notation)、ランダウ記法 (Landau notation) あるいは主要な記号として O （数字の0ではない）を用いることから（バッハマン-ランダウの）O-記法 (Bachmann-Landau O-notation[1])、ランダウのオミクロンなどともいう。 記号 O はドイツ語のOrdnungの頭字にちなむ[2]。 なおここでいうランダウはエトムント・ランダウの事であり、『理論物理学教程』の著者であるレフ・ランダウとは別人である。 ランダウの記号は数学や計算機科学をはじめとした様々な分野で用いられる。 ランダウの記号 は 、x
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
