[algorithm] O (log * N)는 무엇입니까?

Program / 글쓴이

O (log * N)는 무엇이며 O (log N)와 어떻게 다릅니 까?

답변

O( log* N )” 반복 로그 “입니다.

컴퓨터 과학에서 n의 반복 로그, log * n (일반적으로 “log star”로 읽음)으로 기록되는 것은 결과가 1보다 작거나 같기 전에 로그 함수를 반복적으로 적용해야하는 횟수입니다.

답변

log* N비트는 훨씬 느린 단지보다 매우 느리게 자라는 반복 된 알고리즘이다 log N. 기본적으로 답이 1 미만이 될 때까지 (예 🙂 답을 반복적으로 ‘기록’ log(log(log(...log(N)))하고 있어야하는 횟수 log()가 답입니다.

어쨌든, 이것은 Stackoverflow에 대한 5 년 된 질문이지만 코드는 없습니까? (!) 수정 해 보겠습니다. 여기에 재귀 및 반복 함수에 대한 구현이 있습니다 (둘 다 동일한 결과를 제공함).

public double iteratedLogRecursive(double n, double b)
{
    if (n > 1.0) {
        return 1.0 + iteratedLogRecursive( Math.Log(n, b),b );
    }
    else return 0;
}

public int iteratedLogIterative(double n, double b)
{
    int count=0;
    while (n >= 1) {
        n = Math.Log(n,b);
        count++;
    }
    return count;
}

답변

log * (n)- “반복 로그” 로 알려진 “log Star n “

간단히 말해서 log * (n) = log (log (log (….. (log * (n))))라고 가정 할 수 있습니다.

log * (n)는 매우 강력합니다.

예:

1) Log * (n) = 5 여기서 n = 우주의 원자 수

2) 3 색을 사용한 나무 색칠은 log * (n)에서 할 수 있으며 나무색은 2 색이면 충분하지만 복잡도는 O (n)이됩니다.

3) 유클리드 최소 스패닝 트리 : 무작위 O (n log * n) 시간을 알고있는 점 집합의 들로네 삼각 분할 찾기.

답변