計算量
3. 例 ● 問：1 ~ Nまでの整数の総和を求めよ – 普通に計算する → N-1回足し算 → O(N-1) – 公式を使う → 足し算と掛け算と割り算 → O(3) ● 計算の仕方によって計算量が違うことがある 4. いくつかのルール ● O記法の中身は一番大きな規模だけ残す ● 係数は1にする ● 例 – O(N-1) → O(N) – O(4N^2 + 2N) → O(N^2) – O(N^2 + M^2) → NとMが独立なのでこれ以上無理 – O(2^N + N^2) → O(2^N) – O(3) → O(1) 5. なぜか ● 中の変数が非常に大きな値になった時のことを考える ● O(5N^2 + 100N + 4)の場合 – N = 1 → 109 – N = 100→ 60004 – N = 10000 → 501000004 – N = 100000000 → 500
計算量を具体的に見てみる 2009-01-06 - きしだのはてな
アルゴリズムの話では、計算量の解析がかかせません。 計算量はオーダー記法で表されますが、これは、データの入力量に対してどのくらい時間がかかるかをあらわしたものです。 こういった話はどのアルゴリズムの本にも載ってるはずですが、具体的にどのようなプログラムを書くとそのオーダーになるかという記述はあまりありません。 ということで、やってみました。 計算時間表示のための共通処理を行うクラスは、一番最後に書いてます。 O(1) 計算時間がO(1)のアルゴリズムは、処理が入力の量によらない場合です。 配列の要素のアクセスや、ハッシュテーブルによるデータ検索、連結リストへの追加削除などがこれにあたります。 コードには入力量でのループが含まれません。 public class O1 extends ViewCompFrame{ @Override void compute(int n) { proc();
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
