11 - 一般名無し質問者 2022/02/07(月) 03:48:14 ID:PszSREfp0
昨日の続きですを
筆算の例では計算時間を見積もるのに使った掛け算の回数はわかりやすい形をしていましたが、ふつうはもう少し複雑な形をしていて、たとえばf(n) = n^3 + n^2のような計算量になることもありえます。
ところで、当職らが計算時間の関数を考えていた動機は大きなデータでプログラムを動かした時の実行時間を調べることでした。
今挙げたfを考えてみると、nが非常に大きいときはn^3の項が支配的となりn^2は無視してもよいことがわかります。n=10000の時を考えるとn^2はn^3の1万分の1しかないからです。
計算量理論においてはこういうときにランダウの記号を用いて関数の挙動を表現します。支配的な項だけを抜き出してf(n)はO(n^3)である、と言います。
このようにして計算量を表現すると、最初の動機だった計算時間の予測以外にもメリットがあります。
その1つは、プログラムが解こうとしている問題の難易度を比較できるようになるということです。ここでいう難易度とは、コンピュータで解くのに必要な時間として定義します。
ある問題を解くためのO(n^2)時間かかるプログラムが存在するなら、その問題の難易度はO(n^2)以下であると考えるのです。
「以下」がついているのがポイントで、O(n)のプログラムが存在していないのが人類が無能で発見できていないだけか理論的に不可能であるからかはわからないからです。
たとえば、掛け算問題については筆算のプログラムによってO(n^2)以下であることがわかりましたが、高速フーリエ変換を用いるとO(n log(n))時間で解けることが知られているので、掛け算問題の難易度はO(n log(n))以下ということになります。
やっと伏線張り終わったので次回で終わりの予定です。