near-optimal

ほぼ最適な。最適に近い保証がある

1本の論文題名に登場

定義

理論上の下界にごく近い、という性能の主張を表す語。厳密な最適の証明は難しいことが多いため、「定数倍の範囲で最善に届いている」形で述べるのが通例で、near-optimal と書かれていたら何に対して最適なのか（メモリか、計算量か、後悔量か）を必ず確認する。

理論的な性能の主張