できるだけ嘘を書かずに計算量やオーダーの説明をしようとした記事 - えびちゃんの日記
計算量についてのお話です。対象は、プログラミング経験はあるが計算量のことを知らない初心者から、計算量のことを知っているつもりになっている中級者くらいです。 数式を見たくない人にとっては読むのが大変かもですが、深呼吸しつつ落ちついて読んでくれるとうれしいです。 それから、この記事が自分には合わないな〜と思ったときは、（別の記事を Qiita とかで検索するよりも）この記事の一番下の 参考文献 にある本を読むことをおすすめします。Amazon の試し読みで無料で読めます*1。 TL; DR 関数の増加度合いのことをオーダーと呼ぶよ 計算量は、入力サイズ（など）を受け取ってアルゴリズムの計算回数（など）を返す関数だよ その関数のオーダーについての議論がよく行われるよ オーダーを上から抑えるときは \(O\)、下から抑えるときは \(\Omega\) を使うよ オーダーを上下両方から抑えたいときは
仕事でコードを書いていますがどうしても同期と比べて仕事が遅いです。早くコードを書くコツや短くまとめるコツなどがあれば教えてほしいです。あと普段どんなことを意識してコー��
私は昔、趣味で作っていたアプリに機能を「追加」する度に、アプリケーション(実行ファイル)の総サイズを「減らす」、というのを繰り返していたよ。速度も同様に。 これによって「あるパターンはこう簡潔に直せる」というパターン知識が積み上がっていった気がするな。 さらに、それを実現する過程で、限界に見えた状況を打開するために色んな既存アルゴリズムを勉強して実際に使って身につけていくことになった。 ある問題があるときに、的確に適合するアルゴリズムや構成が発見(選択)できると、劇的に簡潔になることがある。そこにたどり着けるかどうか考えるのが楽しい。 あと、同じコードを何年も「育てる」という経験をすると、保守性の低いコードがどう困るかが身に染みるようになるよね。ソースコードは「人が読む物」でもあり、読みやすいというのも保守するなら重要なパラメータになる。これはコメントを書けという意味じゃない。コメ
文書比較（diff）アルゴリズム
文書比較（diff）アルゴリズム 前のドキュメント 次のドキュメント ＶｉＶｉの文書比較（diff）機能で使用しているアルゴリズムについて解説する。 これらのアルゴリズムは Myers 氏らの論文によるもので、氏は筆者のためにわざわざ論文をＷｅｂサイトで入手可能な形式にしてくださった。この場を借りてお礼申し上げる。 オリジナル論文は以下のＷｅｂサイトから入手可能である。 http://www.cs.arizona.edu/people/gene [1] E.W.Myers, "An O(ND) Difference Algorithm and Its Variations", Algorithmica, 1 (1986), pp.251-266 [2] S. Wu, U. Manber, G. Myers and W. Miller, "An O(NP) Sequence Comparis
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
