Что означает O(log(log(n))))-конкурентоспособность)?

Я просматривал некоторые структуры данных и заметил временную сложность: O(log(log(n))))-competitive.

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


algorithm time-complexity
person unj2    schedule 30.05.2009    source источник
comment
Можете ли вы улучшить вопрос?   -  person Peter Stuifzand    schedule 30.05.2009
comment
Можете ли вы улучшить его хотя бы на O(log(log(N)))?   -  person Mitch Wheat    schedule 30.05.2009

Ответы (2)


arrow_upward
13
arrow_downward

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

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

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

person kanak    schedule 30.05.2009

arrow_upward
1
arrow_downward

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

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

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

person Nick Dandoulakis    schedule 30.05.2009