高速フーリエ変換より高速なフーリエ変換アルゴリズム | スラド サイエンス
DFT（短時間フーリエ変換）した結果がkスパースな （＝ほとんど０ばっかりで、０以外のデータが最大でもｋ個しかない） ような、信号に対して行える高速アルゴリズムの話しのようです。 計算オーダー ・DFT O(n^2) ・FFT O(n log n) ・NOSFT ①O(k log n) ※理想 ②O(k log n log(n/k)) ※一般的な入力 ただしk≦n, フーリエ変換結果がkスパースな場合。 理想的には、ｋスパースなデータであれば①なんでしょうけど、 わりあいkスパースなデータであれば②程度。外れていれば誤差が増える。 １０倍早いという感じは受けなかったのですが、 イメージ的には全データ1024個だったら、フーリエ変換した後の結果が ０以外のデータ102以下、ほとんど０データが残992個であれば、 ②の演算が採用でき、k=102, n=1024としてFFTに比べ10
「ビーチで、前から30人の女性が順番に歩いてくる。…
「ビーチで、前から30人の女性が順番に歩いてくる。このうち一番の女性に声を掛けたい。どんな戦略でいくのがいいか？」 という問題の解法を教えてください。 確か、「はじめの数人はやりすごして、次に今までで一番の女性が現れてきたらそれに決める」というような答えだったと思ったのですが…。 聞くところによると、高校の受験数学の確率で出てくる問題だとか。 この証明というか、答えの詳しい説明というか、そういうことについて扱っているページがあればお教え頂ければ幸いです。
Life is beautiful: 恋の連立方程式、「パートナー探し」の最適化アルゴリズムに関する一考察
「自分にできるだけ相応（ふさわ）しいパートナー」を見つけることは、我々人間にとって、人生の最も重要なのテーマの一つでもある。しかし、そのプロセスである「恋愛」や「お見合い」に関して、なぜか今までシステマティックな考察がされて来なかったように思える。そこで、今回はその「パートナー探し」のプロセスをモデル化・数値化することにより、最適なアルゴリズムを見つけようと思う。 まずは、「自分にできるだけ相応しいパートナーを探す」というあいまいな問題を、もう少し明確にモデル化された問題に単純化する。もちろん、単純化するとはいえ、あまり現実とかけ離れていては役に立たないので、現実味を壊さない程度の単純化を行う。 ［モデル化された問題］ 結婚適齢期の女性が、これから１０人の男性と順番にお見合いをして、その中から結婚相手を見つけることにしたとする。相手の意思は無視して良く、「この人と結婚したい」と宣言した時点
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
