是否存在时间复杂度为Ө(n²)的决策问题?
换句话说，我正在寻找一个决策问题，其最著名的解已经证明具有N²的下界。
我想在矩阵中寻找最大的数，但问题是矩阵是O(n²)的输入，所以解是线性的。
不需要是已知的问题，假设一个问题就足够了。
是否存在闭对?
在任何"困难"度量空间中，给定n点，是否存在距离小于r的对，其中r是输入参数?
直观地证明:
如果r是输入参数，则必须搜索每个点。
对于一个点，你需要计算到其他点的距离，也就是Θ(n)
n点,你有n *Θ(n) =Ө(n²)。
时间复杂度:Ө(n²)