是否存在具有Ө(n平方)时间复杂度的决策算法？
是否存在具有Ө(n平方)时间复杂度的决策算法？
提问于 2016-09-26 06:42:56
是否存在时间复杂度为Ө(n平方)的决策问题？
换句话说，我正在寻找一个决策问题，其中最著名的解决方案已经被证明有一个N的下界。
我想寻找矩阵中的最大数，但问题是矩阵是O(n×2)的输入，所以解是线性的。
它不需要是已知的问题，一个假设的问题也就足够了。
回答 1
Stack Overflow用户
发布于 2016-09-26 07:39:39
存在闭对吗？
在给定n点的“困难”度量空间中，是否存在一对小于r的距离，其中r是输入参数？
直观证明：
考虑到r是一个输入参数，您必须搜索每个点。
对于一个点，要计算到每一个点的距离，即Θ(n)。
对于n点，有n*Θ(n) =Ө(N 2)。
时间复杂度:Ө(n平方)
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/39696232
复制相关文章
相似问题
腾讯云开发者
