読者です 読者をやめる 読者になる 読者になる

あざらしとペンギンの問題

主に漫画、数値計算、幾何計算、TCS、一鰭旅、水族館、鰭脚類のことを書きます。

計算量とは

間に挟む形で「計算量」というものを扱う上での心構えなどについて書いておきます。 計算量とは 「計算量」とはその名の通り計算の難しさを測る何らかの数値のことです。あるいは計算にかかるコスト=資源の消費量と言ってもいいでしょう。つまり、ある問題…

オーダーのすゝめ

前回の計算量の議論の問題点として、数字の見方(基数)を自由に変えられるとした場合、計算量が一定しないことを最後に述べました。それは例えば計算量がCPUに依存するということであり、計算量を理論的に抽象化して議論する場合の妨げとなります。そこで、…

オーダー記法・その4

今回は新しいオーダー記法を導入します。それらは主に計算量理論において用いられ、他の分野ではあまり見かけることがない(マニアックな)ものです。とはいえ、使うところでは普通に使うので、今後のためにも定義をちゃんと述べておく必要があるでしょう。…

オーダー記法・その3

今回の目標は、より複雑なオーダー記法をきちんと定義することです。例えば、あるいは、もっと複雑なのような記法です。 オーダー記法の拡張 右辺の式にオーダーが入る場合 最初の例を解釈して適切な意味付けを与えましょう。 に関して に続く項を誤差項とし…

オーダー記法・その2:基本的な定義

それでは、前回の話を踏まえて、オーダー記法を厳密に定義しましょう。今回は、最も基本的な場合として、 のとき のように、右辺に一つのオーダーだけがある場合を扱います。これは、今後出てくるすべての派生的な記法の大元です。そのために、(筆者ができ…

オーダー記法・その1:使用例からの導入

今回は情報科学においてよく用いられる「オーダー記法」について説明します。オーダー記法は、諸量の評価式から重要な部分を抜き出すのに便利な記法であり、情報系分野では基本的な記法として多く用いられます。ただ、見かけによらずその厳密な意味は少々複…