나는 내일 Computer Science Midterm을 가지고 있으며 이러한 재귀 함수의 복잡성을 결정하는 데 도움이 필요합니다. 간단한 사례를 해결하는 방법을 알고 있지만 여전히 어려운 사례를 해결하는 방법을 배우려고 노력하고 있습니다. 이것들은 내가 알아낼 수없는 몇 가지 예제 문제 일뿐입니다. 도움을 주시면 제 연구에 큰 도움이 될 것입니다. 감사합니다!
int recursiveFun1(int n)
{
if (n <= 0)
return 1;
else
return 1 + recursiveFun1(n-1);
}
int recursiveFun2(int n)
{
if (n <= 0)
return 1;
else
return 1 + recursiveFun2(n-5);
}
int recursiveFun3(int n)
{
if (n <= 0)
return 1;
else
return 1 + recursiveFun3(n/5);
}
void recursiveFun4(int n, int m, int o)
{
if (n <= 0)
{
printf("%d, %d\n",m, o);
}
else
{
recursiveFun4(n-1, m+1, o);
recursiveFun4(n-1, m, o+1);
}
}
int recursiveFun5(int n)
{
for (i = 0; i < n; i += 2) {
// do something
}
if (n <= 0)
return 1;
else
return 1 + recursiveFun5(n-5);
}
답변
각 함수에 대한 Big O 표기법의 시간 복잡도는 숫자 순서입니다.
- 첫 번째 함수는 기본 사례에 도달하기 전에 n 번의 재귀 적으로 호출되므로 선형
O(n)이라고도 합니다. - 두 번째 함수는 매번 n-5라고 불리우므로 함수를 호출하기 전에 n에서 5를 빼지 만 n-5도입니다
O(n). (실제로 n / 5 번의 순서라고하며 O (n / 5) = O (n)). - 이 함수는 log (n) base 5이며, 함수를 호출하기 전에 5로 나눌 때마다
O(log(n))(base 5) ( 대수 라고도 함) 및 Big O 표기법 및 복잡도 분석은 base 2를 사용합니다. - 네 번째에서는 n 또는 recurs되지 않는 한 각 함수 호출이 자신을 두 번 호출하기 때문에
O(2^n), 즉 지수 입니다. -
마지막 함수의 경우 for 루프는 2 씩 증가하기 때문에 n / 2가 걸리고 재귀는 n-5가되고 for 루프는 재귀 적으로 호출되므로 시간 복잡도는 (n-5) * (n / 2) = (2n-10) * n = 2n ^ 2- 10n은 점근 적 행동과 최악의 시나리오 고려 사항 또는 big O가 노력하고있는 상한으로 인해 가장 큰 항에만 관심이
O(n^2)있습니다.중간에 행운을 빕니다;)
답변
여기서 사건의 경우 n <= 0, T(n) = O(1). 따라서 시간 복잡도는시기에 따라 달라집니다 n >= 0.
n >= 0아래 부분 에서 사례 를 고려할 것 입니다.
1.
T(n) = a + T(n - 1)
여기서 a는 상수입니다.
유도하여 :
T(n) = n * a + T(0) = n * a + b = O(n)
여기서 a, b는 상수입니다.
2.
T(n) = a + T(n - 5)
a는 상수입니다
유도하여 :
T(n) = ceil(n / 5) * a + T(k) = ceil(n / 5) * a + b = O(n)
여기서 a, b는 상수이고 k <= 0
삼.
T(n) = a + T(n / 5)
a는 상수입니다
유도하여 :
T(n) = a * log5(n) + T(0) = a * log5(n) + b = O(log n)
여기서 a, b는 일정하다
4.
T(n) = a + 2 * T(n - 1)
a는 상수입니다
유도하여 :
T(n) = a + 2a + 4a + ... + 2^(n-1) * a + T(0) * 2^n
= a * 2^n - a + b * 2^n
= (a + b) * 2^n - a
= O(2 ^ n)
여기서 a, b는 상수입니다.
5.
T(n) = n / 2 + T(n - 5)
여기서 n은 일정하다
n = 5q + rq와 r이 정수이고 r = 0, 1, 2, 3, 4로 다시 작성하십시오 .
T(5q + r) = (5q + r) / 2 + T(5 * (q - 1) + r)
우리는 q = (n - r) / 5r이 5보다 작으므로 상수라고 생각할 수 있습니다.q = O(n)
유도하여 :
T(n) = T(5q + r)
= (5q + r) / 2 + (5 * (q - 1) + r) / 2 + ... + r / 2 + T(r)
= 5 / 2 * (q + (q - 1) + ... + 1) + 1 / 2 * (q + 1) * r + T(r)
= 5 / 4 * (q + 1) * q + 1 / 2 * (q + 1) * r + T(r)
= 5 / 4 * q^2 + 5 / 4 * q + 1 / 2 * q * r + 1 / 2 * r + T(r)
r <4이므로 상수 b를 찾을 수 있습니다. b >= T(r)
T(n) = T(5q + r)
= 5 / 2 * q^2 + (5 / 4 + 1 / 2 * r) * q + 1 / 2 * r + b
= 5 / 2 * O(n ^ 2) + (5 / 4 + 1 / 2 * r) * O(n) + 1 / 2 * r + b
= O(n ^ 2)
답변
재귀 알고리즘의 복잡성을 근사화하는 가장 좋은 방법 중 하나는 재귀 트리를 그리는 것입니다. 재귀 트리가 완성되면 :
Complexity = length of tree from root node to leaf node * number of leaf nodes
- 첫 번째 함수는 길이
n와 리프 노드 수를 가지1므로 복잡도는n*1 = n -
두 번째 함수는
n/5리프 노드 의 길이 와 수를 다시 가지1므로 복잡성이 커집니다n/5 * 1 = n/5. 대략적으로n -
세 번째 함수의 경우
n모든 재귀 호출마다 5로 나뉘어 지기 때문에 재귀 트리의 길이는log(n)(base 5)1이고 리프 노드의 수는 1이므로 복잡도는log(n)(base 5) * 1 = log(n)(base 5) -
네 번째 함수의 경우 모든 노드에 두 개의 자식 노드가 있으므로 리프 노드의 수는 같고
(2^n)재귀 트리의 길이는n복잡 할 것(2^n) * n입니다. 그러나n앞에서는 의미(2^n)가 없으므로 무시할 수 있고 복잡성 만 말할 수 있습니다(2^n). -
다섯 번째 함수에는 복잡성을 나타내는 두 가지 요소가 있습니다. 재귀 함수의 기능으로 인해 발생하는 복잡성과
for각 함수에서 루프로 발생하는 복잡도 위의 계산을 수행하면 재귀 함수의 기능~ n으로 인한 복잡성과 for 루프로 인한 복잡성이 발생합니다n. 총 복잡성은 다음과 같습니다n*n.
참고 : 이것은 복잡성을 계산하는 빠르고 더러운 방법입니다 (공식 없음). 이에 대한 의견을 듣고 싶습니다. 감사.
답변
우리는 위의 답변에서 내가 누락 한 것을 수학적으로 증명할 수 있습니다.
그것은 수 극적으로 어떤 방법을 계산하는 방법을 이해하는 데 도움이. 수행 방법을 완전히 이해하려면 위에서 아래로 읽는 것이 좋습니다.
T(n) = T(n-1) + 1그것은 방법이 완료되는 데 걸리는 시간이 동일한 방법과 동일하지만 n-1을 사용T(n-1)하고 이제 우리가 추가+ 1하는 것은 일반적인 작업이 완료되는 데 걸리는 시간이기 때문입니다 (제외T(n-1)). 이제T(n-1)다음과 같이 찾을 것T(n-1) = T(n-1-1) + 1입니다.. 우리는 이제 우리에게 어떤 종류의 반복을 줄 수있는 함수를 만들어서 완전히 이해할 수있는 것처럼 보입니다. 우리의 오른쪽 배치됩니다T(n-1) = ...대신T(n-1)하는 방법 내부T(n) = ...: 우리에게 줄 것T(n) = T(n-1-1) + 1 + 1입니다T(n) = T(n-2) + 2또는 우리는 우리가 누락 찾을 필요가 말해k:T(n) = T(n-k) + k. 다음 단계를 수행하는n-k것을 특징으로하고n-k = 1있기 때문에 재귀의 단부가 걸릴 정확하게 O (1) 때n<=0. 이 간단한 방정식에서 우리는 이제 그것을 알고k = n - 1있습니다. 의 장소를하자k우리의 마지막 방법 :T(n) = T(n-k) + k우리를 줄 것이다 :T(n) = 1 + n - 1정확히 어떤n또는O(n).- 1과 같습니다. 당신은 그것을 스스로 테스트하고 얻을 수
O(n)있습니다 볼 수 있습니다 . T(n) = T(n/5) + 1이전과 마찬가지로이 메서드가 완료되는 시간은 같은 메서드의 시간과 같지만n/5이로 인해이 메서드 가 바인딩 된 것T(n/5)입니다. 하자 발견T(n/5)1 등 :T(n/5) = T(n/5/5) + 1입니다T(n/5) = T(n/5^2) + 1. 최종 계산을 위해T(n/5)내부T(n)에 배치합시다 :T(n) = T(n/5^k) + k. 다시 이전과 같이,n/5^k = 1인n = 5^k5의 힘, n은 우리에게 무슨 요구대로 정확히 인 대답은log5n = k(기본 5 로그). 하자가 우리의 조사 결과를 놓고T(n) = T(n/5^k) + k다음과 같은 :T(n) = 1 + logn인O(logn)T(n) = 2T(n-1) + 1우리가 여기에있는 것은 이전과 기본적으로 동일하지만 이번에는 우리는 2하자 발견하여, 따라서 우리가 여러 재귀 적으로 2 번 메소드를 호출하는T(n-1) = 2T(n-1-1) + 1것입니다T(n-1) = 2T(n-2) + 1. : 우리의 다음 장소 이전과,하자 우리의 발견 장소T(n) = 2(2T(n-2)) + 1 + 1입니다T(n) = 2^2T(n-2) + 2즉 우리를 제공을T(n) = 2^kT(n-k) + k. 하자의 발견k이 주장에 의해n-k = 1인을k = n - 1. 하자의 장소k다음과 같은 :T(n) = 2^(n-1) + n - 1약이다O(2^n)T(n) = T(n-5) + n + 1거의 4와 같지만 이제n하나의for루프 가 있기 때문에 추가 합니다. 하자 발견T(n-5) = T(n-5-5) + n + 1하는 것입니다T(n-5) = T(n - 2*5) + n + 1. 그것을 배치합시다 :T(n) = T(n-2*5) + n + n + 1 + 1)어느 쪽이고T(n) = T(n-2*5) + 2n + 2)k :T(n) = T(n-k*5) + kn + k)또 다시 :n-5k = 1그것은n = 5k + 1대략적인 것n = k입니다. 이것은 우리에게 줄 것입니다 :T(n) = T(0) + n^2 + n그것은 대략O(n^2).
이제 나머지 답변을 읽는 것이 좋습니다.이 답변을 통해 더 나은 관점을 얻을 수 있습니다. 그 큰 O를 얻는 행운을 빌어 요 🙂
답변
여기서 핵심은 통화 트리를 시각화하는 것입니다. 일단 완료하면 복잡성은 다음과 같습니다.
nodes of the call tree * complexity of other code in the function
후자의 항은 일반적인 반복 함수와 같은 방식으로 계산할 수 있습니다.
대신 완전한 트리의 총 노드는 다음과 같이 계산됩니다.
C^L - 1
------- , when C>1
/ C - 1
/
# of nodes =
\
\
L , when C=1
여기서 C는 각 노드의 하위 수이고 L은 트리의 레벨 수입니다 (루트 포함).
트리를 시각화하는 것은 쉽습니다. 첫 번째 호출 (루트 노드)에서 시작한 다음 함수의 재귀 호출 수와 동일한 수의 자식을 그립니다. 하위 호출에 전달 된 매개 변수를 “노드 값”으로 쓰는 것도 유용합니다.
따라서 위의 예에서
- 여기서 호출 트리는 C = 1, L = n + 1입니다. 나머지 함수의 복잡도는 O (1)입니다. 따라서 총 복잡도는 L * O (1) = (n + 1) * O (1) = O (n)입니다.
n level 1 n-1 level 2 n-2 level 3 n-3 level 4 ... ~ n levels -> L = n
- 여기서 호출 트리는 C = 1, L = n / 5입니다. 나머지 함수의 복잡도는 O (1)입니다. 따라서 총 복잡도는 L * O (1) = (n / 5) * O (1) = O (n)입니다.
n n-5 n-10 n-15 ... ~ n/5 levels -> L = n/5
- 여기서 호출 트리는 C = 1, L = log (n)입니다. 나머지 함수의 복잡도는 O (1)입니다. 따라서 총 복잡도는 L * O (1) = log5 (n) * O (1) = O (log (n))입니다.
n n/5 n/5^2 n/5^3 ... ~ log5(n) levels -> L = log5(n)
- 여기서 호출 트리는 C = 2, L = n입니다. 나머지 함수의 복잡도는 O (1)입니다. 이번에는 C> 1이므로 호출 트리의 노드 수에 대한 전체 수식을 사용합니다. 따라서 총 복잡도는 (C ^ L-1) / (C-1) * O (1) = (2 ^ n-1입니다. ) * O (1) = O (2 ^ n) 입니다.
n level 1 n-1 n-1 level 2 n-2 n-2 n-2 n-2 ... n-3 n-3 n-3 n-3 n-3 n-3 n-3 n-3 ... ... ~ n levels -> L = n
- 여기서 호출 트리는 C = 1, L = n / 5입니다. 나머지 함수의 복잡도는 O (n)입니다. 따라서 총 복잡도는 L * O (1) = (n / 5) * O (n) = O (n ^ 2)입니다.
n n-5 n-10 n-15 ... ~ n/5 levels -> L = n/5
답변
