O（log（log）））） - 競合平均とは何ですか？

Question

私はいくつかのデータ構造を調べていましたが、これは時間の複雑さとして認識しました。 O（log（log（n）））） - competitive

私は、定数競合が、予想される時間/最適時間の比であることを読んだ。しかし、セット競争力を持つことはどういう意味ですか？

Answer 1

オンラインアルゴリズムは、事前に入力を知らず、予測できない入力に「反応する」必要があります。対照的に、オフラインアルゴリズムは、すべての入力を事前に知っているアルゴリズムです。

競合分析は、最適なオンラインアルゴリズムのパフォーマンスを最適なオフラインアルゴリズムと比較します。したがって、k競合は、オンラインアルゴリズムよりもk倍も悪く実行するオフラインアルゴリズムが存在することを意味する。したがって、O（lglgn）競合とは、最適なオフラインアルゴリズムが、最適なオンラインアルゴリズムよりも最大lglgn（倍の定数倍）悪い時間を実行することを意味します。

---

「k-競合」という用語は、「k-近似」という用語と同じように考えることができます。 k近似は、近似アルゴリズムが最適アルゴリズムよりも最大でk倍悪いことを実行することを意味する。

Answer 2

Thisは、あなたの質問に明るい光を当てることができます。

上記のリンクから：

実行する 最小コストとして シーケンスSとOPT（S、TO）を実行するコストとして A（S）を定義し、任意のBSTアルゴリズムとします全ての可能なシーケンスS、A（S）< = T * OPT（S、To）+ O（m、n）に対してアルゴリズムAがT-競争である。