recursion - 표기법 - 재귀와 빅 오




정렬 시간 복잡도 계산 (5)

나는 재귀와 빅 O 표기법을 포함하는 최근의 컴퓨터 과학 숙제를 통해 연구 해왔다. 나는 이것이 꽤 잘 이해하고 있다고 믿는다. (확실히 완벽하지는 않지만!) 그러나 가장 큰 문제를 안고있는 한 가지 질문이있다. 이상한 점은 그것을보고 숙제 중 가장 단순한 것으로 보입니다.

뒤에 오는 재발에 해결책을위한 큰 Oh 표기법을 사용하여 제일 성장율을 제공하십시오?

T (1) = 2

T (n) = 2T (n-1) +1 (n> 1)

그리고 선택은 :

  • O (n log n)
  • O (n ^ 2)
  • O (2 ^ n)
  • O (n ^ n)

나는 빅 오 (O)가 상한선 (upper bound)으로 작용하고, 프로그램이나 프로세스가 취할 수있는 가장 많은 계산량 또는 가장 높은 실행 시간을 설명한다는 것을 이해합니다. 이 재귀는 O (n)이어야한다고 생각합니다. 왜냐하면 대부분의 경우 재귀는 n의 각 값에 대해서만 한 번 발생하기 때문입니다. n은 사용할 수 없기 때문에, O (nlogn)보다 좋거나, 다른 세 가지 옵션이 더 나쁩니다.

그래서, 제 질문은, 왜 이것이 O (n)가 아닌가?


나는 이것이 기하 급수적 일 것이라고 생각한다. n을 1 씩 증가 시키면 계산량이 두 배가됩니다.

아니, 그렇지 않아. 그와는 반대로 :

n 회 반복 할 때, 우리는 실행 시간 R을 얻는다. 그러면 n + 1 회 반복을 위해 정확히 R + 1을 얻습니다.

따라서 성장률은 일정하며 전체 런타임은 실제로 O ( n )입니다.

그러나 그의 솔루션은 지나치게 복잡하지만 Dima의 질문에 대한 가정은 맞다고 생각합니다.

당신이해야 할 일은 닫힌 폼 솔루션, 즉 T (n)에 대한 비 재귀 공식을 생각해 내고 그 식의 big-O가 무엇인지 결정하는 것입니다.

T ( n )과 T ( n + 1) 반복의 상대적 크기를 검사하고 상대적 성장률을 결정하는 것으로 충분합니다. 그 양은 명백히 두 배가되어 점근 적 성장을 직접적으로 나타냅니다.


나는 당신이 약간의 질문을 잘못 이해했다고 생각합니다. 재발을 해결하는 데 얼마나 걸릴지 당신에게 묻지 않습니다. 그것은 솔루션 자체의 big-O (점근 적 바인딩)이 무엇인지 묻고 있습니다.

당신이해야 할 일은 닫힌 폼 솔루션, 즉 T (n)에 대한 비 재귀 공식을 생각해 내고 그 식의 big-O가 무엇인지 결정하는 것입니다.


문제는 재현에 대한 해결책을 제시하는 큰 오 표기법을 요구하는 것이지 재발의 계산 비용이 아닙니다.

다시 말하면 재발은 다음과 같습니다 :

  1 -> 2
  2 -> 5
  3 -> 11
  4 -> 23
  5 -> 47

빅 오 표기법이 시퀀스 2, 5, 11, 23, 47을 가장 잘 묘사 한 것은 무엇입니까?

이를 해결하는 올바른 방법은 되풀이 방정식을 푸는 것입니다.


첫째, 모든 네 가지 대답은 O (n)보다 나쁩니다 ... O (n * log n)은 평범한 구 O (n)보다 더 복잡합니다. 더 큰 것은 : 8 또는 8 * 3, 16 또는 16 * 4 등 ...

실제 질문에. 재귀를하지 않으면 일반 솔루션은 분명히 일정 시간 내에 해결 될 수 있습니다.

(T (n) = 2 ^ (n - 1) + 2 ^ (n) - 1), 그래서 그들이 요구하는 것이 아닙니다.

보시다시피 재귀 코드를 작성하면 다음과 같습니다.

int T( int N )
{
    if (N == 1) return 2;
    return( 2*T(N-1) + 1);
}

그것은 분명히 O (n)입니다.

그래서 심하게 말로 된 질문 인 것처럼 보입니다. 그들은 아마도 코드의 복잡성이 아니라 함수 자체의 성장을 요구할 것입니다. 그건 2 ^ n입니다. 이제 나머지 숙제를하고 ... O (n * log n)


재발을 해결할 수있는 몇 가지 다른 방법이 있습니다 : 대체, 반복 트리 및 마스터 정리. 마스터 정리는 마스터 정리 형식에 맞지 않으므로이 경우 작동하지 않습니다.

다른 두 가지 방법을 사용할 수도 있지만이 문제의 가장 쉬운 방법은 반복적으로 해결하는 것입니다.

T (n) = 2T (n-1) +1
T (n) = 4T (n-2) + 2 + 1
T (n) = 8T (n-3) + 4 + 2 + 1
T (n) = ...

패턴을 봐?

T (n) = 2n-1 · T (1) + 2n-2 + 2n-3 + ... + 1
T (n) = 2n-1 · 2 + 2n-2 + 2n-3 + ... + 1
T (n) = 2n + 2n-2 + 2n-3 + ... + 1

따라서 가장 촘촘한 경계는 Θ (2 n )입니다.







big-o