永久機関
永久機関の発明は不可能に決まっていると言うことで特許になりませんが、逆行列が理解できない審査官がいるのであれば、Nに比例する手間でのソートならありえると思ってしまう審査官もいるかも知れないと、ふと思ったのでした。数盲の多い国アメリカあたりで誰か実験して欲しい物です。
ActiveXを使っていたりして危ないページのURLが書いてあったので必要以上には近寄らなかったので、あやふやな記憶ですが、以前、fj.sci.mathだったかに、高速なソートを発明したという人が現れたことがあったと思います。n*log(n)ではなく、nに比例する手間でソートができると言っていたのだと思います。
N個のデータをM個の箱にわけるだけで、箱の内部には順序がない場合はNに比例する時間で処理できますが、N個のデータをN個の段階に1つずつ入れる場合には、log(N!)(スターリングの公式で、N*log(N)-Nで近似できます。)に比例する時間が最低かかります。という風に親切に説明している人がいました。
04/01/26更新