Что означает O (log (log (n)))) - конкурентный?

Question

Я просматривал некоторые структуры данных и заметил, что это временная сложность: O (журнал (журнал (п)))) -. Конкурентоспособны 1003 *

Я читал, что постоянная конкуренция - это отношение ожидаемого времени / оптимального времени. Но что значит иметь конкурентоспособный набор?

Answer 1

Онлайн-алгоритм - это алгоритм, который не знает свои входные данные заранее и должен «реагировать» (в некотором смысле) на непредсказуемые входные данные. Напротив, автономные алгоритмы - это те, которые заранее знают все свои входные данные.

Конкурентный анализ сравнивает производительность оптимального алгоритма онлайн с оптимальным алгоритмом оффлайн. Таким образом, k-конкурентоспособный означает, что существует автономный алгоритм, который работает в большинстве раз хуже, чем онлайн-алгоритм. Таким образом, конкурентный O (lglgn) означает, что оптимальный автономный алгоритм работает в большинстве случаев хуже (в разы постоянных) раз, чем оптимальный онлайн-алгоритм.

---

Термин «k-конкурентный» можно понимать так же, как термин «k-аппроксимация». K-аппроксимация означает, что алгоритм аппроксимации работает не более чем в k раз хуже, чем оптимальный алгоритм.

Answer 2

Это может пролить свет на ваш вопрос.

Из приведенной выше ссылки:

Пусть A - любой алгоритм BST, определите A (S) как стоимость выполнения последовательность S и OPT (S, To) в качестве минимальная стоимость выполнения последовательности S. Алгоритм А является Т-конкурентным, если для всех возможных последовательностей S, A (S) <= T * OPT (S, To) + O (м, n). </p>