次元の呪い

次元の呪い（じげんののろい、英: The curse of dimensionality）という言葉は、リチャード・ベルマンが使ったもので、（数学的）問題の空間の次元が増えるに従って解法である算法から信頼できる結果を得るためのに必要となる計算資源の量が指数関数的に大きくなることを表している。たとえば、単位区間をサンプリングして各点同士の距離を 0.01 以下に抑えるためには100個の点を等間隔に配置すれば十分である。