 | P=NP問題の読み物を読んでいた時に疑問がでてきました。
基本ソートの計算量はO(n^2)です。
これについては感覚的にですが、n個のものを参照することをn回繰り返すので、n^2程度の多項式時間の計算量だと感じます。
それに対して、ある数nの素因数を求めるアルゴリズムでは、√n以下の数字で順に割っていけば解が出ます。ソートの時と同じように考えると、自分の（間違った）感覚では計算量がO(√n)に感じます。
実際には2進数で表した時の桁数を考えて、A=log[2]nとし、√n=(√2)^Aなので、指数関数時間かかるというのが正しいです。
確かに指数関数時間でなければ暗号化に使えなくなるのでその意味では納得できるのですが…。
ソートでは2進数に表し直すという処理はせず、素因数を求める方ではその処理をするというのはどのような違いから出てきているのでしょうか？
根本的なことが分かっていないのかもしれませんが、よろしくお願いします。
|