計算量を具体的に見てみる 2009-01-06 - きしだのはてな
アルゴリズムの話では、計算量の解析がかかせません。 計算量はオーダー記法で表されますが、これは、データの入力量に対してどのくらい時間がかかるかをあらわしたものです。 こういった話はどのアルゴリズムの本にも載ってるはずですが、具体的にどのようなプログラムを書くとそのオーダーになるかという記述はあまりありません。 ということで、やってみました。 計算時間表示のための共通処理を行うクラスは、一番最後に書いてます。 O(1) 計算時間がO(1)のアルゴリズムは、処理が入力の量によらない場合です。 配列の要素のアクセスや、ハッシュテーブルによるデータ検索、連結リストへの追加削除などがこれにあたります。 コードには入力量でのループが含まれません。 public class O1 extends ViewCompFrame{ @Override void compute(int n) { proc();
FPGAとArduinoとRasberryPIの違いと、FPGAを勉強する理由 - きしだのHatena
はたから見てると、FPGAとArduinoとRasberry PIって、なんか小さくてデバイス挿して使ってて似たもののように見えるかもしれません。 そんな中、どこが違うの？って思ってる人もいるかと思ったので、それぞれの違いと、そしてそこから得られる技術者としての知識をまとめてみます。 まあ、得られる知識として「それぞれのデバイスの使い方と周辺環境」ってのはありますが、それは当然として。「それぞれのデバイスの使い方と周辺環境」を得るメリットがわかる比較としてまとめたいと思います。 根底は「なんで最近FPGAをやってるか」っていうことの説明なので、そういうバイアスがあると思ってください。 FPGAというのはチップの種類なので、実際にはDE0などのFPGA評価ボードとの比較ですが。中でもDE0-nanoは大きさや価格を考えると、豪華なArduinoくらいの位置づけとして出してきたようにも見えます
ラムダ計算とチューリングマシンの違い 2009-04-13 - きしだのはてな
ぼくもYコンビネータがわかるようになるまではそうだったのだけど、Yコンビネータを使うとどのような処理ができるのかがよくわからなくて悩んでいる人が多いように思う。他の人のブログを見ても、名前をつけずに再帰ができるのがすばらしいとか書いてあったりするのだけど、それによってどういう処理ができるのかわからずにいた。 結論をいえばYコンビネータには、なにかの処理を便利にする能力はない。関数であらゆる計算ができるということが示せれば、あとは用なしだ。理論の礎としてうまってしまえばいい。 結局、Yコンビネータによってどのような処理ができるかというのは、ラムダ計算の要素のメリットをチューリングマシンの中に見出そうとしてるといえる。 ラムダ計算とチューリングマシンは、どちらも計算モデルという点では一致しているけど、全く違う。 無限であるか有限かの違いといってもいい。 チューリングマシンでは、データの量と処理
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
