2019-06-01から1ヶ月間の記事一覧

計算量の表現 (O|Θ|Ω)記法まとめ

アルゴリズムの計算量を表現する方法として、記法や記法、記法があります。 それらの定義と違いについてまとめていきます。 定義 何らかのアルゴリズムの計算量が自然数から自然数への関数で表されるとするとき それぞれの定義はこのようになっています $$ O…

Hello, Rust world!

Rustを使ってみました 今回の目標はHello, Rust world!という出力を得ることです まず、Rustの環境構築を行います OSはWindows10 1809です rustup.rs このサイトよりRustツールチェインのインストーラをダウンロードしインストールします(リンクのためにVisu…

高速フーリエ変換の計算量解析

高速フーリエ変換とは、離散フーリエ変換を高速に行うアルゴリズムです。 具体的にどのくらい高速なのか気になったので解析してみます。 まず、離散フーリエ変換について 要素数の入力ベクトルを、同じく出力の周波数ベクトルをとすると、離散フーリエ変換は…