入力をそのまま出力することは一瞬でできるか

背景は id:MarriageTheorem:20090204:1233682830 を参照ください。

元記事にある通り、入力をそのまま出力するアルゴリズムの計算量は、計算モデルに依存します。Turing機械で考えるとしても、入力テープと出力テープが別ならば、入力サイズに対して時間計算量だけど、1テープTuring機械で in-place処理なら、ですね。

それ以前に気にしなくてはならないのは「一瞬で」の定義ですね。は「一瞬」かどうかを、どう判断しましょう？

ちなみに、元記事とさらに元記事には、「分解」について的外れなコメントをして人がいるけど、それとは事情が異なります。ここで「分解」は数学用語だけど、ここでの「一瞬」は数学用語ではありませんので。

当日追記：

専門用語の意味を国語辞典で引くことが不適切であることを理解できずに的外れな文句をいう人は、世の中に一定の割合で存在するみたいで、どこでもそこそこ観測されます。基本的には関わらないのが吉です。

教員をやってて教え子にそんなのがいた場合は、職務ですので説得しないといけませんけどね。実際、何度かあったけど、いずれも、一度説明したら同じへまはしなくなりました。うちの学生は優秀ってことかな。

2009年2月9日追記：
例の人がコメント欄でやっぱり暴れだしました。だから、関らないのが吉といったのに。