質問するログイン新規登録

回答編集履歴

1

時間は有限、という前提が抜けていました

2018/04/28 01:53

投稿

maisumakun
maisumakun

スコア146761

answer CHANGED
@@ -6,4 +6,4 @@
6
6
 
7
7
  のように、いくつも考えられます。真ん中については、たとえばソートであれば規模に応じた計算量やメモリ量がアルゴリズムによって違ってきますし、ハッシュ値の比較用に「どんな値を比較しても有意な時間差がでない」ことを要求される場面もあります。
8
8
 
9
- なお、いちばん最初の「同じ値を与えれば同じ結果を返す」という意味での等しさは、100%正しく判定する方法は**存在しない**ことが証明されています。大雑把に言えば、「未解決問題の解がないか探し続け、見つけた段階で停止する関数」と「ただ無限ループする関数」を比較して、有意な結果が得られるならそちらのほうが驚きです。
9
+ なお、いちばん最初の「同じ値を与えれば同じ結果を返す」という意味での等しさは、有限の時間内で100%正しく判定する方法は**存在しない**ことが証明されています。大雑把に言えば、「未解決問題の解がないか探し続け、見つけた段階で停止する関数」と「ただ無限ループする関数」を比較して、有意な結果が得られるならそちらのほうが驚きです。