プログラムの実行に掛かる時間を把握しておくのは、プログラミングを行う上で基本的な注意点です。今回は、計算量のオーダーについて学びながら、TopCoderのMedium問題を考えてみましょう。 プログラムの実行時間 業務としてプログラミングをされている方には釈迦に説法かもしれませんが、プログラムの実行に掛かる時間を把握しておくのは、プログラミングを行う上で基本的な注意点です。そしてこれは、TopCoderなどのコンテストでプログラムを組む際にもよく当てはまります。通常、こうしたことは感覚的に理解している方がほとんどだと思いますが、具体的にどれくらいのループを回すと何秒掛かる、といった基準を持っている人は少ないのではないでしょうか？　非常に基本的なことですが、プログラムの実行時間に関して再確認しておきたいと思います。 TopCoderの制限に関して TopCoderでは、実行時間およびメモリ使

みなさん、こんにちは、今回は乱数の話です。 特に複数機種でのコンシューマ機でゲームを開発をしていると、機種間で乱数値を統一するために乱数生成アルゴリズムを自作しますよね。 そこでよく使われるアルゴリズムが「線形合同法」です、内容は至って簡単で、以下の漸化式を使います。 A,B,Mは定数で、どの値が入るかは処理系依存です。 例えばUnixなどの処理系ではA=1103515245,B=12345,M=2147483647などが入ります。 C言語ですと以下のようになります。 static unsigned int x=1; void srand(unsigned int s) { x=s; } unsigned int rand() { x=x*1103515245UL+12345UL; return x&2147483647UL; } この「線形合同法」は計算が簡単で高速ですから、いろいろな環

アルゴリズムの話では、計算量の解析がかかせません。 計算量はオーダー記法で表されますが、これは、データの入力量に対してどのくらい時間がかかるかをあらわしたものです。 こういった話はどのアルゴリズムの本にも載ってるはずですが、具体的にどのようなプログラムを書くとそのオーダーになるかという記述はあまりありません。 ということで、やってみました。 計算時間表示のための共通処理を行うクラスは、一番最後に書いてます。 O(1) 計算時間がO(1)のアルゴリズムは、処理が入力の量によらない場合です。 配列の要素のアクセスや、ハッシュテーブルによるデータ検索、連結リストへの追加削除などがこれにあたります。 コードには入力量でのループが含まれません。 public class O1 extends ViewCompFrame{ @Override void compute(int n) { proc();

概要 エラトステネスの篩（sieve of Eratosthenes）とは、与えられた整数以下の素数をすべて発見する計算手順(アルゴリズム)の一つ。整数のリストから各素数の倍数を順に削除していくことで素数のみがリストに残る。 2から目的の数までの整数のリストを用意する。このリストの中から最初の素数である2の倍数を消していく。リストに残った整数のうち、先頭にある3が次の素数である。次に、リストの中から3の倍数を消してゆき、残った整数のうち先頭にある5が次の素数である。 このように、先頭に残った数の倍数をリストから消してゆき、その都度先頭に残った数を集めると、素数のリストが得られる。このアルゴリズムが「篩」（ふるい）と呼ばれるのは、この一連の操作が、粉状のものを何段階もふるいにかけてより分ける作業に似ていることに由来する。古代ギリシャの学者であるエラトステネス（Eratosthenes）が紀元

2007年12月04日08:30 カテゴリアルゴリズム百選Math アルゴリズム百選 - 二分探索(binary search) 今回は二分探索を取り上げます。 検索:コンピューターの最もよくある利用法 「二分探索って何?」「ググレカス」と言われないためにこの記事は存在するのですが、Webの検索に限らず、「目的のデータを見つけて取り出す」というのは、およそコンピューターの利用法で最もポピュラーなものです。 配列:コンピューターがデータを扱う根本的な方法 そのデータはコンピューターのなかでどう置かれているかというと、非常に単純です。デジタル化されたデータ=数値が一定間隔で並んでいるだけです。こういうデータ構造を、配列(array)といい、この数値一個一個のことを要素(element)と言います。 現代のコンピューターでは、最小要素はバイト(byte)と呼ばれています。このバイトの中には0と1

挿入ソートのコードを改良してシェルソートのコードを作成した。 正しく動作することは確認したが、自分にとっては実装するには複雑すぎてコードを見ただけでは正しいかどうか判断が難しい。アルゴリズムとしては明快なのであるが...。try and errorでようやく正しい答えを得ることができた。 """ Shell sort Aug. 09, 2007 """ data = [2,15,23,40,56,1,12,54,27,6,3,5,67,87,22,38,92] print data dsep = len(data)/2 while 1: for N in range(1, dsep): for i in range(N, len(data), N): tmp = data[i] j = i while tmp < data[j-N] and j>=N: data[j] = data[j-N

ついでに挿入法も試す。左から順番に比較してゆき、挿入する位置が確定するまで並んでいるデータを右へずらす。 """ insertion sort Aug. 07, 2007 """ data = [15, 23, 3, 56, 22, 9, 1, 3, 20, 11] print data for i in range(1,len(data)): tmp = data[i] j = i while tmp < data[j-1] and j>=1: data[j] = data[j-1] j -=1 data[j]=tmp print data

バブルソートと似た整列アルゴリズムの選択法も試してみる。正常に動作することを確認。今回はfor文を2回使用した。 """ selection sort ver.1 Aug.07, 2007 """ value = [6,2,4,9,7,1,0,3,8,10,1,5] for i in range(0, len(value)-1): min = i for num in range(min+1, len(value)): if value[min] > value[num]: min = num dummy = value[min] value[min] = value[i] value[i] = dummy print value

バブルソートを実行するプログラムをPythonで作成する。精錬されればもっとエレガントに書けるのだろうが、とりあえず正常に動作することは確認した。 """ bubble sort ver.1 Aug. 7, 2007 """ height = [178, 175, 173, 165, 179, 155, 182, 177] nmax = len(height)-1 while nmax >=2: for num in range(0,nmax): if height[num] > height[num+1]: dummy = height[num] height[num] = height[num+1] height[num+1] = dummy # print num, height nmax = nmax-1 print height

概要 二分探索（binary search）とは、データ検索アルゴリズムの一つで、一定の順序にソート(整列)済みのデータ群の探索範囲を半分に絞り込むを操作を繰り返すことで高速に探索を行う手法。 まず、データを降順（大きい順）あるいは昇順（小さい順）に並べ替え、探索したいデータが中央の要素より大きいか小さいかを調べる。これにより、データが全体の前半分にあるか後ろ半分にあるかを判定することができるため、存在しない側の半分は探索範囲から外すことができる。 半分になったデータ群の中央の要素と再び比較し、前半と後半のどちらにあるかを調べる。この操作を繰り返し行うことで、一回の操作ごとに探索範囲の大きさが半分になっていき、中央の要素が求めるデータに一致するか、探索範囲の要素数が一つになる（求めるデータは見つからなかったことが確定する）と探索は終了する。 値の大小は文字の索引順の前後関係などに適宜置き換

概要 ユークリッドの互除法（Euclidean algorithm）とは、二つの自然数の最大公約数を求める計算手順(アルゴリズム)の一つ。古代ギリシャの数学者ユークリッド(Euclid/エウクレイデス)の発見した古典的な手法で、紀元前4世紀頃に編纂された「原論」に掲載されており、記録に残る最古のアルゴリズムとも言われる。 二数の最大公約数は両者とも割り切ることができる自然数（公約数）のうち最大のものだが、これは大きい方を小さい方で割った余り（剰余）と小さい方との最大公約数に等しいという性質があり、これを利用して効率的に算出する。 aとbの2つの数（a≧bとする）の最大公約数を求める場合、まずaをbで割った余りb'を求める。次に、b'をaで割った余りa'を求める。さらに、a'をb'で割った余りを求め…と交互に余り同士の割り算を繰り返し、初めて割り切れた（余りが0になった）ときの除数（割る方の

この項目では、数値解析における二分法について説明しています。ゼノンのパラドックスの二分法については「ゼノンのパラドックス」を、誤った二分法については「誤った二分法」を、論理学・哲学上の二分法（dichotomy）については「二項対立」を、数理的な二分法については「2値論理」をご覧ください。 数値解析における二分法（にぶんほう、英: bisection method）は、解を含む区間の中間点を求める操作を繰り返すことによって方程式を解く求根アルゴリズム。反復法の一種。 2分法 赤線は解の存在する範囲。この範囲を繰り返し1/2に狭めていく。 ここでは、となるを求める方法について説明する。 ととで符号が異なるような区間下限と区間上限を定める。 との中間点を求める。 の符号がと同じであればをで置き換え、と同じであればをで置き換える。 2.に戻って操作を繰り返すことにより、となるに近づく。 はとの間

ヤプログ！ byGMO サービス終了のお知らせ ヤプログ！ byGMOは、2020年1月31日をもちまして、サービスを終了いたしました。 これまでヤプログ！ byGMOをご愛顧いただき、誠にありがとうございました。心より感謝申し上げます。 今後とも、GMOメディア株式会社のサービスをよろしくお願いいたします。 2020年1月31日

この記事は検証可能な参考文献や出典が全く示されていないか、不十分です。 出典を追加して記事の信頼性向上にご協力ください。（このテンプレートの使い方） 出典検索?: "エラトステネスの篩" – ニュース · 書籍 · スカラー · CiNii · J-STAGE · NDL · dlib.jp · ジャパンサーチ · TWL (2019年6月) エラトステネスの篩 (エラトステネスのふるい、英: Sieve of Eratosthenes) は、指定された整数以下の全ての素数を発見するための単純なアルゴリズムである。古代ギリシアの科学者、エラトステネスが考案したとされるため、この名がついている。

スターリングの公式はランダウの記号を用いてと書くこともできる。 ランダウの記号（ランダウのきごう、英: Landau symbol）は、主に関数の極限における漸近的な挙動を比較するときに用いられる記法である。英語圏では一般的にビッグ・オー（Big O）と呼ばれる。 ランダウの漸近記法 (asymptotic notation)、ランダウ記法 (Landau notation) あるいは主要な記号として O （数字の0ではない）を用いることから（バッハマン-ランダウの）O-記法 (Bachmann-Landau O-notation[1])などともいう。 記号 O はドイツ語のOrdnungの頭字にちなむ[2]。 なおここでいうランダウはエトムント・ランダウの事であり、『理論物理学教程』の著者であるレフ・ランダウとは別人である。 ランダウの記号は数学や計算機科学をはじめとした様々な分野で用い