できるだけ嘘を書かずに計算量やオーダーの説明をしようとした記事 - えびちゃんの日記
計算量についてのお話です。対象は、プログラミング経験はあるが計算量のことを知らない初心者から、計算量のことを知っているつもりになっている中級者くらいです。 数式を見たくない人にとっては読むのが大変かもですが、深呼吸しつつ落ちついて読んでくれるとうれしいです。 それから、この記事が自分には合わないな〜と思ったときは、（別の記事を Qiita とかで検索するよりも）この記事の一番下の 参考文献 にある本を読むことをおすすめします。Amazon の試し読みで無料で読めます*1。 TL; DR 関数の増加度合いのことをオーダーと呼ぶよ 計算量は、入力サイズ（など）を受け取ってアルゴリズムの計算回数（など）を返す関数だよ その関数のオーダーについての議論がよく行われるよ オーダーを上から抑えるときは \(O\)、下から抑えるときは \(\Omega\) を使うよ オーダーを上下両方から抑えたいときは
高速フーリエ変換の実装を難しそうかなと思っている方が、なんだ簡単じゃないですか！！ となるための実装講座です - CADDi Tech Blog
対象読者さんはどのような方ですか？ FFT（高速フーリエ変換）の定義を知っているものの、その実装が難しそうだと感じて困っている方々です。逆に原理や有用性、理論的な子細にご興味のある方のご期待には応えられないと思います。 目標 FFT に苦手意識のあった方が、最低限動くコードを書くだけなら簡単かも？ と感じてくださるまでになれたら、私はとっても嬉しいです。 離散フーリエ変換とは 定義はウィキペディアにあります。（責任放棄） wikipedia: 離散フーリエ変換 今回採用する定義 最速で実装までたどり着きたいですから、理論的なところはスキップです。 $N = 2 ^ n$ としましょう。$N$ 次多項式を入れると $N$ 次多項式を返してくれる何かがフーリエ変換です。多項式と言いましたが、コンピュータープログラムですから、係数を並べたものだと思ってくださると嬉しいです。 複素係数 $N$ 次
15パズル
最近, 高木貞治先生の「数学小景」を眺めていたら, その中に「十五の駒遊び」という題で15パズルの話があった. ところで, 最近知った15パズルの面白い解き方は, 福岡教育大学の藤本さんの提案する「回転型操作」によるものだ. 2件の論文がある. 情報処理学会研究報告にある「スライドパズルにおける回転型操作とアクセスビリティ」と, 近着の数式処理にある「Loop generatorによる15パズルの最適アルゴリズムとGod's numberについて」. 私は明解な手順には関心があるが, 最短手順には興味がないので, 後の論文は眺めた程度であった. 前の論文も解法は数式処理しシステムGAPを使って記述してあるので, GAPに馴染まぬ凡人にはとんと理解し得ぬ. 以下では私がSchemeで書いたプログラムの考え方を述べる. この回転操作(英語ではloop generatorというらしい)は, 前回
C言語でインクルードするだけで使えるNon-movingで正確なコピーGCを作った - Qiita
C言語でインクルードするだけで使えるNon-movingで正確なコピーGCを作った インクルードするだけで使えるNon-movingで正確なGCをC言語用に作りました。 行数がコメントを除いて100行に満たない非常に小さなライブラリです。 GCのアルゴリズムとしてはCheneyのコピーGCを採用しています。 通常のCheneyのコピーGCではメモリ空間のうち半分が無駄になってしまいメモリ効率が悪かったり、 GC発生時にオブジェクトが移動してしまいC言語のようなポインタを直接触れる言語との相性が悪いという欠点がありました。 今回はヒープ全体を二重連結リストとして管理することでそのような問題を解決しています。 ちなみにこれはTreadmill GCのアイデアと同じです。(が、アルゴリズム自体はTreadmill GCではありません。) APIはLinuxのlist.hに非常に近い見た目になって
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
