recursion 표기법 재귀와 빅 오




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

나는 재귀와 빅 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) 반복의 상대적 크기를 검사하고 상대적 성장률을 결정하는 것으로 충분합니다. 그 양은 명백히 두 배가되어 점근 적 성장을 직접적으로 나타냅니다.


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

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

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

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

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


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

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


나는 이것이 기하 급수적 일 것이라고 생각한다. n을 1 씩 증가 시키면 값이 두 배로 커집니다.

T(2) = 2 * T(1) = 4
T(3) = 2 * T(2) = 2 * 4
...

T (x)는 다음 프로그램의 실행 시간입니다 (예 :).

def fn(x):
 if (x == 1):
  return    # a constant time
 # do the calculation for n - 1 twice
 fn(x - 1)
 fn(x - 1)

첫째, 모든 네 가지 대답은 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) = 3*2^(n-1) - 1

그렇다면 당신은 유도에 의해 이것이 실제로 해결책이라는 것을 증명합니다. 기본 케이스:

T(1) = 3*2^0 - 1 = 3 - 1 = 2. OK.

유도:

Suppose T(n) = 3*2^(n-1) - 1. Then
T(n+1) = 2*T(n) + 1 = 3*2^n - 2 + 1 = 3*2^((n+1)-1) - 1. OK.

첫 번째 평등은 재발 정의에서 비롯되며 두 번째는 귀납적 가정으로부터 유래한다. QED.

3 * 2 ^ (n-1) - 1은 분명히 Theta (2 ^ n)이므로, 정답은 세 번째입니다.

O (n)에 응답 한 사람들에게 : 나는 디마와 더 동의하지 못했습니다. 이 문제는 T (n) (닫힌 형식이 제공 되었기 때문에 이제는 O (1)이 될 것임)을 계산하는 알고리즘의 계산 복잡도에 가장 엄격한 상한을 요구하지 않습니다 . 문제는 T (n) 자체 의 가장 튼튼한 상한선을 요구하고, 그것은 지수 적이다.





big-o