オーダー
オーダーについて。適当に済ましていたので、おぼえがきします。アルゴリズムでも数学でも見ることがよくありますが、若干うろ覚えです。
定義
が のときオーダーである。
これを変形すると、 となることから、この定義は は より発散する速度が遅いということを意味しているのがわかります。この時 は で抑えられる、と言ったりするようです。
これに対し似た記法で、というものもあります。この時、以下が成り立ちます。
詳細な定義は省略しますが極限が0になることが違います。 は より発散する速度が、 の時より、十分遅いというイメージです。この時 は に比べ無視できる、と言ったりするようです。例えば、写像 が で全微分可能とは、
です。ここでは となっていて多少変化がありますが基本的に意味は変わっていません。つまり、 と は のノルムが十分小さいところでは限りなく等しいということが言えます。
アルゴリズムなどではよく、、 などと言ったりしますね。これらは「入力データ量 に対する実行時間は 」みたいな文脈だったと思います。これはつまり、
より、
この場合はアルゴリズムの実行時間が に比例する、ということですね。 なども同様です。
感想
わかったようなわかってないような微妙な気分です。当たり前のことを言っている気持ちにもなりました。
まあ少なくとも毎回ググらなくてよくなっただけ、進歩かと思います。