背景は id:MarriageTheorem:20090204:1233682830 を参照ください。元記事にある通り、入力をそのまま出力するアルゴリズムの計算量は、計算モデルに依存します。Turing機械で考えるとしても、入力テープと出力テープが別ならば、入力サイズに対して時間計算…