O (log (log (log (n)))-경쟁적인 의미는 무엇입니까?

Question

나는 몇 가지 데이터 구조를 겪고 있었고 이것을 시간 복잡성으로 알았습니다. o (log (log (n)))-경쟁력.

나는 상수 경쟁이 예상 시간/최적 시간의 비율이라고 읽었습니다. 그러나 세트 경쟁력을 갖는 것은 무엇을 의미합니까?

Answer 1

온라인 알고리즘은 입력을 미리 알지 못하고 예측할 수없는 입력에 "반응"해야하는 알고리즘입니다. 반대로 오프라인 알고리즘은 모든 입력을 미리 알고있는 알고리즘입니다.

경쟁 분석은 최적의 온라인 알고리즘의 성능을 최적의 오프라인 알고리즘과 비교합니다. 따라서 K- 경쟁은 온라인 알고리즘보다 대부분의 k- 타임에서 더 나빠지는 오프라인 알고리즘이 있음을 의미합니다. 따라서 O (LGLGN) 경쟁력은 최적의 오프라인 알고리즘이 최적의 온라인 알고리즘보다 대부분의 LGLGN (시간 A 일정)에서 더 나빠진다는 것을 의미합니다.

---

"K- 경쟁"이라는 용어는 "K- 발사"라는 용어와 동일한 방식으로 생각할 수 있습니다. K- 대단도는 근사 알고리즘이 최적의 알고리즘보다 최대 K 배 더 나빠짐을 의미합니다.

Answer 2

이것 당신의 질문에 약간의 빛을 비출 수 있습니다.

위의 링크에서 :

a는 BST 알고리즘으로, 시퀀스 S를 수행하는 비용으로 a를 정의하고 시퀀스 S를 수행하는 데 최소 비용으로 OPT (s, to)를 정의하십시오. 알고리즘 A는 가능한 모든 시퀀스 S에 대해 t- 경쟁적입니다. a (s) <= t * opt (s, to) + o (m, n).