takehikom https://blog.hatena.ne.jp/takehikom/ わさっきhb https://takehikom.hateblo.jp/ 情報教育 ソートの計算量も，個数ではなく入力サイズで測るべきでは? 離散対数問題を検討したとき，法pで見ると線形時間になるけれど，実際には入力サイズで測らないといけないので，(準)指数関数になるということから，他のアルゴリズムでも厳格に入力サイズで測らないといけないという主張ですね． ソートの問題では，入力の値が配列に格納されていて，配列の各要素のサイズが等しいことが前提となっています．このとき，要素数をn，配列の一つの要素のサイズをk，入力長をmとすると，m≒nk となります．ここで「=」ではなく「≒」なのは，厳密に入力サイズを求めるときには，nやkという値(の2進表現)も，入力に含まれるからです．た… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Ftakehikom.hateblo.jp%2Fentry%2F20070731%2F1185831778" title=" P=NP問題を理解するためのステップ〜入力サイズ - わさっきhb" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2007-07-31 06:42:58 rich https://takehikom.hateblo.jp/entry/20070731/1185831778 1.0 100%