本日は(今後も?),質問を増やして,一つ一つの解説の分量を減らしてみます.
なぜきちんと時間計算量を求めるのではなく,オーダで表すの?
何らかの計算モデルで厳密に時間計算量を求めても,実装するプログラムでその値にならないことが想像できるためです.
100倍違っていてもオーダが同じでいいのでしょうか?
と がどちらも になるというのは,単純化のしすぎに見えるかもしれません.
しかし,実行環境・データ構造次第で,理論的にも実用的にも,定数倍のスピードアップ(時間計算量を減らすこと)が比較的容易にできます.
また,「100」というのは,入力サイズのnが大きくなれば,取るに足らない値になります.
オーダというのは,入力サイズに着目した何らかの数量が,序列orderのどこに位置づけられるかを示す指標なのです.
どうやってスピードアップするのですか?
並列処理です.
テューリング機械でも,1本のテープではなくm本のテープで同時に処理をすることで,時間計算量をm分の1にできるということです.
「m本のテープ」のmを大きくすれば,処理時間はいくらでも小さくできる?
たしかに,できます*1.
しかし,計算量を評価するには,アルゴリズムを先に確定させて,それから入力を考えることになります.上で出た文字を使って表現すると,mが先,nが後であって,その逆ではありません.10000本のテープ(10000台の並列処理)を使って,1本のテープ(1台のマシン)と比べて10000倍高速にしたとしても*2,入力サイズnをm=10000よりもうんと大きな値にとれば,m=10000なんて「取るに足らない」ことになります.
ついでに,実行時にテープの本数を倍にする処理ができれば,そしてその処理を繰り返せば,nが先,mが後にできそうに思えるのですが,実際のところは「テープの本数を倍にする処理」の手間を無視することができず,残念ながら,動的にいくらでも小さくできるというのは難しいです.これは,紙を半分に半分に折り曲げれば,いつかは月に到達するんじゃないかという議論に似ています.