2

長さ n の配列で範囲のセットが与えられた場合、 setS={ (x1,y1) , (x2,y2) ,......(xk,yk) }からクエリが与えられQ={ (l1,r1) , ......(li,yi) }ます。各クエリ (li,ri) は、この範囲 (li,ri) の間にセット S からの範囲がいくつあるかを意味します。
次のことが可能かどうかを知りたいだけです。

  1. Pre-computation in O(n) and then queries in O(1)
  2  Pre-computation in O(nlogn) and then queries in O(logn)

PS:上記の 2 点だけで解決するのではなく、自分で解決策を考えたいと思います。

4

1 に答える 1

1

わかりました。はい/いいえで答えられないからです。謎をネタバレすることなく、少し詳しく説明します。

O(n) での事前計算と O(1) でのクエリ

セットSの範囲はソートされていると述べたので(最後の要素で言ってみましょう)。事前計算なしで先に進むことができました。O(logn)これだけで、分割統治戦略の助けを借りて のクエリ時間を達成できると思います。しかし、クエリ時間を取得するのO(1)は少し難しいようです。範囲ツリーまたはkd-treesを使用しても、期待できる最善のことはO(log)複雑です。補助的なデータ構造 (ハッシュテーブルなど) を指定されたセットと共に使用すれば、何かを作り上げることができるかもしれませんが、それでもO(1)少し野心的です。スペースの要件は何ですか?

O(nlogn) での事前計算と O(logn) でのクエリ

これは間違いなく可能のようです。O(nlogn)すでにソートされていると言うので、事前計算さえ必要ないかもしれません。登録 クエリ時間、セット Q の範囲ごとに時間がかかりO(logn)ます。したがって、セット Q の k 範囲の場合、 がかかりk * O(logn)ます。セット Q の大きさはどのくらいだと思いますか?

于 2013-08-08T05:59:45.347 に答える