algorithm - O(log(log(n))))-competitive とはどういう意味ですか?

Question

私はいくつかのデータ構造を調べていましたが、これが時間の複雑さであることに気付きました: O(log(log(n))))-competitive。

一定の競争力は、予想時間/最適時間の比率であると読みました。しかし、セット競争力を持つとはどういう意味ですか?

Answer 1

オンライン アルゴリズムは、その入力が事前にわからないアルゴリズムであり、予測不可能な入力に対して (ある意味で) "反応" する必要があります。対照的に、オフライン アルゴリズムは、すべての入力が事前にわかっているアルゴリズムです。

競合分析では、最適なオンライン アルゴリズムと最適なオフライン アルゴリズムのパフォーマンスを比較します。したがって、k-competitive は、オンライン アルゴリズムよりも多くても k 倍悪いパフォーマンスをするオフライン アルゴリズムがあることを意味します。したがって、O(lglgn) の競合性は、最適なオフライン アルゴリズムが、最適なオンライン アルゴリズムよりも多くても lglgn (定数の倍) 倍悪いパフォーマンスを示すことを意味します。

---

「k-competitive」という用語は、「k-approximation」という用語と同じように考えることができます。k 近似とは、近似アルゴリズムのパフォーマンスが最適アルゴリズムの最大 k 倍であることを意味します。