다음과 같은 방법의 복잡성은 무엇입니까?

Big O 표기법을 사용하여 복잡성 측정을 배우는 중이며, 다음 방법의 복잡도가 O (n * log4n)인데 정확한지 궁금합니다. 여기서 "4"는 첨자입니다.다음과 같은 방법의 복잡성은 무엇입니까?

public static void f(int n) 
{ 
    for (int i=n; i>0; i--) 
    { 
     int j = n; 
     while (j>0) 
      j = j/4; 
    } 
}

출처

2010-06-04 George Kagan

일반적으로 그냥 O를 작성합니다 (N 로그 (N))입니다. –

상수는 대개 내가 생각한대로 떨어졌습니다. 그래서 O (n log n)을 쓰지 않고 O (n log n)을 써야합니다. (실제로 맞다면) – bwawok

예, 당신은 함수의 복잡성 당신의 기능이 복잡 O(n*log_4(n))이 있다면 그것은 또한 사실이다 그래서 O(n*log_4(n))

Log_4(n) = ln(n)/ln(4) 및 ln(4) 그것의 복잡성을 가지고, 상수 즉, 올바른 O(n*ln(n))

출처

2010-06-04 17:16:40

당신은

public static void f(int n) 
{ 
    for (int i=n; i>0; i--) 
    { 
     int j = i; // Not j = n. 
     while (j>0) 
      j = j/4; 
    } 
}

을 찾으시는 것입니까?

이 경우에도 올바른 것입니다. 그것은 O (nlogn)입니다. 4를 첨자로 쓰는 것은 정확하지만, 쓰기가 더 어려워집니다.

j=n 라인이 있더라도 O (nlogn)입니다.

실제로 더 정확하게하려면 Theta (n logn)라고 말할 수 있습니다.

출처

2010-06-04 17:19:21

4를 첨자로 쓰지는 않습니다. (log4 (n) = log (n)/log (4)' – IVlad

@IVlad : 여전히 정확합니다. 마찬가지로 O (2n) 또는 O (n^2 + 3n + 45)라고 말하는 것이 옳습니다. 그것은 단지 또 다른 함수이며, 우리는 읽기/쓰기/이해가 더 간단하도록 상수를 피합니다. 상수가 성가 시지만 부정확하지는 않습니다. –

@Moron - 내가 본 모든 텍스트는 상수 또는 낮은 차수의 용어를 큰 오 표기법으로 넣지 않는다고 말하기 때문에 'O (2n)'은 정확하지 않으며 'O (n)'이고 두 번째는 예제는'O (n^2)'이어야합니다. 위키 피 디아와 http://www.perlmonks.org/?node_id=227909는 모두 'O (2N) 또는 O (10 + 5N)를 보았을 때 구현 세부 사항을 개념적 내용으로 혼합하고 있습니다.'라고 제안합니다. 이 문제에 대해 더 자세히 설명하는 참조를 제공 할 수 있습니까? – IVlad

네 당신이 옳다, 복잡성은 첨자를 무시 n 개의 *의 LOG4 (N)

출처

2010-06-04 17:26:55 svlada

다음과 같은 방법의 복잡성은 무엇입니까?

답변

관련 문제