Я просматривал некоторые структуры данных, и я заметил это как временную сложность: O (журнал (журнал (n)))) - конкурс.Что делает O (log (log (n)))) - конкурентоспособный?
Я читал, что постоянное конкурентное отношение было отношением ожидаемого времени/оптимального времени. Но что значит иметь конкурентоспособность?
Онлайн-алгоритм - это тот, который заранее не знает свои входы и должен «реагировать» (в некотором смысле) на непредсказуемые входы. Напротив, автономные алгоритмы - это те, которые заранее знают все свои входы.
Конкурентный анализ сравнивает эффективность оптимального онлайн-алгоритма с оптимальным автономным алгоритмом. Таким образом, k-competition означает, что существует автономный алгоритм, который выполняет не более k-раз хуже, чем онлайн-алгоритм. Таким образом, конкуренция O (lglgn) означает, что оптимальный автономный алгоритм выполняет не более lglgn (раз константу) раз хуже оптимального онлайн-алгоритма.
Термин «k-competition» можно охарактеризовать так же, как термин «k-аппроксимация». К-аппроксимация означает, что алгоритм аппроксимации выполняет не более k раз хуже оптимального алгоритма.
This может пролить свет на ваш вопрос.
Из приведенной выше ссылке:
Пусть А любой алгоритм БСТ, определяют A (S) как стоимость выполнения последовательности S и OPT (S, К) в качестве минимальной стоимости, чтобы выполнить последовательность S. Алгоритм A является T-конкурентным, если для всех возможных последовательностей S, A (S) < = T * OPT (S, To) + O (m, n).
Можете ли вы улучшить вопрос? –
Можете ли вы улучшить его, по крайней мере, на O (log (log (N)))? –