計算量オーダーの求め方を総整理！ 〜 どこから log が出て来るか 〜 - Qiita
NTT データ数理システムでリサーチャーをしている大槻 (通称、けんちょん) です。今回は計算量オーダーの求め方について書きます。 0. はじめに 世の中の様々なシステムやソフトウェアはアルゴリズムによって支えられています。Qiita Contribution ランキング作成のために用いるソートアルゴリズムのような単純なものから、カーナビに使われている Dijkstra 法、流行中のディープラーニングに用いられている確率的勾配降下法など、様々な場面でアルゴリズムが活躍しています。アルゴリズムとはどんなものかについて具体的に知りたい方には以下の記事が参考になると思います: アルゴリズムとは何か ～ 文系理系問わず楽しめる精選 6 問 ～ アルゴリズムを学ぶと $O(n^2)$ や $O(n\log{n})$ や $O(2^n)$ といった計算量オーダーの概念が登場します。こうした記法を見ると
【アルゴリズム】O記法ってなに？初心者必見、プログラムの計算時間を見積もる。｜es
O記法（オーダー記法）とは計算にかかる時間とデータ量の関係について表した記法です。 O(n) とかO(log n)ってよく見かけると思います。あれのことです。 読み方はO(オー)です。0(ゼロ)ではないのでご注意を。（）の中は処理するデータ量です。 記法って何？って思うかもしれませんが、シンプルに、世界共通の表現方法としていてくだい。「このアルゴリズムの計算時間はどれぐらい？」と聞かれた時、他人に説明できる世界共通の基準があると便利ですよね。 O記法は、サンプルプログラムを見た方が早いです。 O(1)function log(arr) { console.log(array[0]); console.log(array[1]); } log([1, 2, 3, 4]); log([1, 2, 3, 4, 5, 6, 7, 8, 9, 10]);O(1)はデータ量がどんなに増えても、常に一回
超高速！多倍長整数の計算手法【前編：大きな数の四則計算を圧倒的な速度で！】 - Qiita
1. はじめに ～メインを読むための準備～ まず、大きな数の計算の話をする前に、少しコンピューターと計算回数について話しましょうか。 コンピューターは、現代ではソフトウェアやアプリケーションの開発に使われていますが、これには重要な背景があります。これは「計算がめっちゃ速いこと」です！人間なんかと比べたら、圧倒的な計算スピードを誇ります。 1-1. 人間の計算速度はどのくらい？ まず人間はどのくらいの速度で計算できるでしょうか？速い人も遅い人もいると思います。 例えば、$628 \times 463$ の計算を、今やってみましょう。10 秒以内で計算できたらかなり速い方でしょう。この計算では、次のように「単純計算」を合計 28 回もしていることになります。 9 回の 1 桁 × 1 桁の掛け算 6 回の 1 桁 × 1 桁の足し算 13 回の繰り上がり計算 もし $628 × 463$ が
Luhnアルゴリズム - Wikipedia
Luhnアルゴリズム（Luhn algorithm, ルーン・アルゴリズム）は、様々な識別番号の認証に使われている単純なチェックサム方式。MOD-10アルゴリズムとも。クレジットカード番号、IMEI番号、en:National Provider Identifier（アメリカでの医療機関の識別番号）、カナダ社会保険番号（Social Insurance Number）などで使われている。IBMの科学者 ハンス・ピーター・ルーン（英語版） が1954年1月6日に特許を申請し、1960年8月23日に発効した[1]。 アルゴリズムはパブリックドメインになっており、今日では広く利用されている。ISO/IEC 7812-1[2] に詳細に記されている。暗号学的ハッシュ関数としては使えない。 記入ミスやタイプミスを検出するためのもので、クレジットマスターによる悪意ある攻撃を防ぐものではない。多くのクレ
ID生成大全 - Qiita
セッションIDやアクセストークン、はたまた業務上で使う一意の識別子など、いろんなところで一意のIDを生成しなきゃいけないケースが存在します。 そこで世間で使われているIDの生成方法について調べてみました。 選択基準 ID生成における要求として、以下の観点が上げられるかと思います。 生成の速度 大量にデータを短期間で処理し、それらにIDを付与する場合、ID生成そのものがボトルネックとなることがあります。 推測困難性 IDを機密情報と結びつける場合、IDを改ざんされても、機密データが見れないようにできている必要があります。 順序性 採番した順にデータをソートする必要がある場合は、IDがソートキーとして使えないといけません。 それぞれについて各生成手段を評価します。 ID生成の手段 データベースの採番テーブル 採番用のテーブルを作り、そこで番号をUPDATEしながら取得していくやりかたです。古い
モバイルゲームの歴史を年代別にご紹介します。モバイルゲームの成長と今後について詳しく解説していきます。
モバイルゲーム 物凄い勢いで勃興したモバイルゲーム業界は、いろいろな課題や問題に直面しながらも巨大化し、今日の時点でのスマートフォン向けゲームの市場へと継承されていきます。 モバイルゲームの歴史 2001 Javaアプリと3Dゲームの登場 Javaが利用できるようになったことにより、ダウンロード型のゲームが供給できるようになりました。 2002 携帯電話端末の大容量化・3D化競争 Java搭載携帯電話端末が登場してからごく僅か1年の間に、アプリのサイズに関しては10倍に広大化し、表現方法も2Dから3Dにシフトし始めました。J-PHONEは『ゼビウス』や『スペースハリアー』などといった昔のアーケードゲームを、ドコモはSIMCITYなどパソコンで世界的規模のヒットを飛ばしたゲームを主力商品としていました。 2003 モバイルゲームの一般化 メモリの制限が厳しいJava仮想マシン上ではなく、OS
Algorithm - 連想配列の実装としてのハッシュはオワコン? : 404 Blog Not Found
2012年01月17日11:45 カテゴリアルゴリズム百選Tips Algorithm - 連想配列の実装としてのハッシュはオワコン? 珠玉のプログラミング Jon Bentley / 小林健一郎訳 つまり「終わったコンテナ」。 以前からうすぼんやりと考えて来た危惧が、すこしはっきりと見えてきた。 徳丸浩の日記: Webアプリケーションに対する広範なDoS攻撃手法(hashdos)の影響と対策 もうそろそろハッシュ(テーブル)以外の手段の連想配列の実装手段を本格的に模索するべきではないか、と。 そのデータ構造は、君の魂を差し出すに足るものかい? 連想配列(Associative array)がコレクション(Collection)、すなわち数多のデータ構造をまとめるデータ構造としての覇者となったのはもはや疑いようがない事実でしょう「配列で実装されるデータ構造ではなくて、配列を実装するデータ構
人材獲得作戦・４ 試験問題ほか - 人生を書き換える者すらいた。
さて試験問題です。 内容は、壁とスペースで構成された迷路が与えられたとき、スタート地点からゴール地点に至る最短経路を求めよ、というものです。 たとえば、S:スタート G:ゴール *:壁 $:解答の経路 としたとき、 ************************** *S* * * * * * * ************* * * * * ************ * * * * ************** *********** * * ** *********************** * * G * * * *********** * * * * ******* * * * * * ************************** という入力に対し、 ************************** *S* * $$$ * *$* *$$*$ ************
はてなのCAPTCHAを破るプログラムは30分で書ける - やねうらおブログ(移転しました)
CAPTCHAとは、スパムコメントなどを防止するための認証画像のことである。 それにしても、はてなのCAPTCHAはひどい。無いよりマシという考え方もあるのでそれについてはあまり議論する気は無いのだが、それにしてもこれを破るプログラムは30分あれば十分書ける。 具体的には、はてなのCAPTCHAには8つの好ましくない特徴と、2つの脆弱性がある。 ■ 8つの好ましくない特徴 ・画像自体のサイズが小さすぎる。→ こんなに小さいと探索量(計算量)が小さくて済む。 ・フォントにゆがみがない → フォントはある程度変形させたほうが良い。変形させてあるとテンプレートマッチングがしにくくなる。 ・フォントが固定。→ フォントは毎回変えたほうが良い。 ・フォントを回転させていない → フォントは文字ごとにある程度ランダムに回転させた方が良い。 ・フォントサイズが一定 → フォントサイズは文字ごとにある程度
Natural Order String Comparison
by Martin Pool This project has moved to github.com/sourcefrog/natsort. Computer string sorting algorithms generally don't order strings containing numbers in the same way that a human would do. Consider: rfc1.txt rfc2086.txt rfc822.txt It would be more friendly if the program listed the files as rfc1.txt rfc822.txt rfc2086.txt Filenames sort properly if people insert leading zeros, but they don't
mixi Engineers’ Blog » 圧縮データベースを使おう
チャリンコ通勤による滝のような汗で、朝からTシャツがシースルーになってしまうmikioです。さて今回は、Tokyo Cabinet（TC）のデータベースを各種のアルゴリズムで圧縮して利用する方法についてご紹介します。 圧縮B+木 B+木とは、比較関数の値による順序が近いレコード群を単一のページにまとめ、各ページにB木（multiway balanced treeの略であり、二分木（binary tree）とは違います）の索引を張ったものです。理論的にはレコードの探索も更新も O(log n) の時間計算量で行え、内部ノード（B木）の操作をキャッシュすると実質的には O(1) の時間計算量で探索や更新が行えるという、かなり安定した性能を備えるデータ構造です。その上、レコードが一定の順序に基づいて並べられているので、数値の範囲検索や文字列の前方一致検索が高速に行えたり、カーソルによって順序に基
PDL で PageRank - naoyaのはてなダイアリー
id:smly さんが PageRank や HITS を Python で実装 されているのに触発されて、自分も PageRank を Perl で実装してみました。 PageRank の計算の中心になるのは Power Method (べき乗法) です。べき乗法では行列とベクトルの積を計算しますので、手軽に使える行列演算ライブラリがあると楽でしょう。 色々調べてみたところ、PDL (The Perl Data Language) が良く使われているようでしたので、これを選択しました。PDL では各種行列演算が簡単に行える他、文字列評価をオーバーライドして行列の文字列出力を良い具合で定義してくれていたりと、なかなかに便利です。PDL は行列計算以外にも色々な科学技術計算やグラフ描写などの操作をサポートしているようです。 さて、PDL を使った PageRank 計算のコードは以下のように
Yokohama.pm #3 でしゃべってきた | ブログが続かないわけ
Perl を使ってモンテカルロ法によるゲームAIを実践してきた。 ルールの簡単○×ゲームを使って、アルゴリズムを説明した。 ま、Perl は関係ない。というか、むしろ合わない>< スライドをあげておいた。 Perl でモンテカルロ法 初めてプレゼンしてみて、いろいろと反省すべきところがあった。 MacBookをプロジェクタに設定するのに手間どるスライドやデモの文字の大きさが適切か気になるしゃべりながら書くのは結構難しいライブコーディングではタイポが異常に多くなる プロジェクタの設定は、前日のShibuya.pm でAcotie さんが苦戦していたのを見ていたので、こういう可能性もあるということは想定できていた。で、そのときにどんな設定にすればいいのかも、そっとメモっておいたので大事にはいたらなかったけど、自分が思っていた画面サイズでプレゼンできなかった。 スライドの文字の大きさに着いては、
るびま
『るびま』は、Ruby に関する技術記事はもちろんのこと、Rubyist へのインタビューやエッセイ、その他をお届けするウェブ雑誌です。 Rubyist Magazine について 『Rubyist Magazine』、略して『るびま』は、日本 Ruby の会の有志による Rubyist の Rubyist による、Rubyist とそうでない人のためのウェブ雑誌です。 最新号 Rubyist Magazine 0058 号 バックナンバー Rubyist Magazine 0058 号 RubyKaigi 2018 直前特集号 Rubyist Magazine 0057 号 RubyKaigi 2017 直前特集号 Rubyist Magazine 0056 号 Rubyist Magazine 0055 号 Rubyist Magazine 0054 号 東京 Ruby 会議 11 直
List::FrontCode - naoyaのはてなダイアリー
先日 Array::Gap という Variable Byte Codes による整列済み整数の圧縮の実装を作りました。(id:naoya:20080906:1220685978) 今日は Front Coding を使った同じような圧縮リストクラス、List::FrontCode を作ってみました。Front Coding は辞書式順に整列済みの文字列リストなどを圧縮する手法です。WEB+DB PRESS Vol.42 のアルゴリズム&データ構造の記事で PFI の岡野原さんによる解説があったので、それを参考に実装しました。 Front Coding Front Coding は http://www.hoge.jp http://www.hoge.jp/a.htm http://www.hoge.jp/index.htm http://www.fuga.com/ http://www.
アルゴリズム百選 - ユークリッドの互除法 : 404 Blog Not Found
2007年12月11日16:30 カテゴリアルゴリズム百選Math アルゴリズム百選 - ユークリッドの互除法 今回は、ユークリッドの互除法を取り上げます。 ユークリッドの互除法とは何か。小学校の時に実は習っているはずですが、忘れている方は思い出してみてください。最大公約数(Greatest Common Divisor)を確実に計算する方法です。古代から有名なこのアルゴリズムは、かつては"The Algorithm"といえばこれをさすほど有名なアルゴリズムです。 それは、コードではなく普通の言葉でも簡単に書くことが出来ます。gcd(m, n)を出すには、 mをnで割り、余りがrだとする 余りrが0なら、nがGCD。 そうでなければ、nとrのGCDを求める 互い違いに割っていくので、互除法というわけです。 function gcd(m, n){ if (m < n) return gcd(
アルゴリズム百選 - 迷ったらbenchmark : 404 Blog Not Found
2007年12月09日03:30 カテゴリアルゴリズム百選 アルゴリズム百選 - 迷ったらbenchmark この話題、以下の答えとしても適度なのでそのまま。 アルゴリズム百選 - フィボナッチ数列にO()を学ぶ - www.textfile.org 「O()が小さいからといって速いとは限らない」が抜けている。ベキ乗アルゴリズム再考 ベキ乗のやり方として、すぐに思いつくのは以下の方法です。 function power(b, n){ var result = 1; while(n--) result *= b; // b を n 回掛け算 return result; } これがO(n)であることは、直感的にわかります。 ところが、これをO(log n)でやる方法も比較的すぐに思いつきます。 例えばbを21乗したいとします。21=16+4+1なので、b21はb(16 + 4 + 1)とも書
アルゴリズム百選 - 値と参照 : 404 Blog Not Found
2007年12月06日15:30 カテゴリアルゴリズム百選 アルゴリズム百選 - 値と参照 今回は値と参照について取り上げます。 突然ですが問題です。以下のJavaScriptプログラムを実行すると、何と表示されるでしょうか? プログラム: var a = [0, 1, 2, 3]; var b = a; b[0] = 'zero'; p(a); 出力: エラー: 答えは、"zero, 1, 2, 3"です。しかし、なぜaを直接変更していないのにaの中身が変わっているのでしょうか? ここで、二行目に注目してみます。ここでは変数bに変数aを代入しています。変数aは配列です。ここだけ見ると、内部で起こっているのは以下のようなことに見えなくもありません。 array b -+ array b -+ | 0 | | 0 | | 1 | = | 1 | | 2 | | 2 | | 3 | | 3 |
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
イマジン アカデミー: テクノロジースキル & 認定資格 | Microsoft Education
カンガルーハウス：テキストライブラリ：2007年7月 A*（A-star：エースター）探索アルゴリズム