takeda25 https://blog.hatena.ne.jp/takeda25/ アスペ日記 https://takeda25.hatenablog.jp/ ウェーブレット行列 ウェーブレット行列の構築方法について。前に書いた記事とは違って、「ウェーブレット行列大好き！」って人*1以外が読んでもあんまり益がない記事だということをあらかじめ書いておく。内容としては、相変わらず中学生以上の知識が必要ということはないけれど。 上の記事で書いたように、ウェーブレット行列は 2進数の基数ソートと同じような感じで構築できる。で、基数ソートをするには、元の配列と同じだけの領域が必要になる。だが、ウェーブレット行列のように各段階でのビット列だけが必要であるなら、その領域は必要ない。ウェーブレット行列でも、ウェーブレット木のノードのようなものを持っておくことで、配列長のオーダーでなく、… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Ftakeda25.hatenablog.jp%2Fentry%2F20130505%2F1367730870" title="ウェーブレット行列の省メモリ構築方法 - アスペ日記" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> https://cdn-ak.f.st-hatena.com/images/fotolife/t/takeda25/20130505/20130505133730.png Hatena Blog https://hatena.blog 2013-05-05 14:14:30 rich https://takeda25.hatenablog.jp/entry/20130505/1367730870 1.0 100%