O（log（log（n）））） - 競爭意味着什麼？

Question

我正在經歷一些數據結構，我注意到這是一個時間複雜度： O（log（log（n）））） - competitive。

我讀到，恆定競爭力是預期時間/最佳時間的比率。但是具有競爭力的是什麼意思？

Answer 1

在線算法是一種預先不知道其輸入的算法，並且必須對某種意義上的「不可預測的輸入」進行「反應」。相比之下，離線算法是預先知道所有輸入的算法。

競爭力分析的最佳在線算法的性能進行比較，以最佳的離線算法。因此，k-競爭意味着存在離線算法，其執行比在線算法更差的k倍。因此，O（lglgn）的競爭意味着最優的離線算法最多比最優在線算法的性能低lglgn（倍於常數）。

---

術語「k-競爭」可以被認爲與術語「k-近似」相同。 k近似意味着近似算法最多比最優算法差k倍。

Answer 2

This可以解釋一下你的問題。

從上面的鏈接：

設A是任何BST算法，定義 A（S）爲執行 序列S和OPT的成本（S，要）以執行所述 最小成本序列 S.算法A是T-競爭性如果 對所有可能的序列S，A（S）< = T * OPT（S，要）+ O（M，N）。