0

我阅读了有关 Range Minimum Queries 的维基百科链接，查看了更多教程（topcoder 和其他链接），但我有一个非常基本的问题：

RMQ 的正式定义是：给定一个从有序集合（例如数字）中取出的对象数组，范围最小查询（或 RMQ） from to 询问子数组中最小元素的位置。

我不明白的是，为什么我们不能通过线性搜索来解决问题？在数组 A[0...n] 中，如果我们需要 RMQ(i,j)

min = A[i]
index = i
for iter=i; iter <j; iter ++
if A[iter] <= min
min = A[iter]
index = iter;

在循环结束时，我们知道最小值和最小值所在的索引。

我肯定在这里遗漏了一些东西......有人可以帮我理解为什么我们需要RMQ吗？

4

2 回答 2

2

RMQ 旨在解决您描述的问题，但比您的方法更快。有两种方法 - 一个静态版本，您可以在其中进行一些预计算（最优化的版本，真正复杂的需要线性预计算），然后为每个查询不断回答，以及动态方法，您有 log(n) 时间为每个查询。

在静态情况下，您不能更改初始数组，而在动态情况下，允许其值及时更改。

请注意，在这两种情况下，您都需要回答很多查询。这意味着在恒定或对数时间内回答会比你的线性方法快得多，因此在你的想法太慢的情况下会起作用。希望这能解释这个想法。

于 2012-08-27T13:23:20.537 回答
1

速度。线性搜索很慢。

与我们使用快速排序（或合并排序，...）而不是简单的插入排序来对大型数据库进行排序的原因相同。

假设您有一个庞大的数据库，并且您将查询 RMQ 数百万次。每个查询的线性搜索效率不高，它将需要数百万次线性搜索，而更高级的算法需要进行少量预处理，然后快速检索所需信息。

于 2012-08-27T13:21:37.380 回答