피보나치 시리즈
시간 및 복잡성 분석에 문제가 있습니다. 나는 재귀적인 방식으로 피보나치 시리즈를 수행했습니다. 나는 그것이 O (n 2 ) 라고 생각합니다 . 시간 분석을 찾을 수 있습니까? 가능하다면 자세히 설명해 주시겠습니까?
#include<iostream>
using namespace std;
void fibonacci(int n,int n1,int n2)
{
if(n==0)
{
cout<<endl<<n1;
return;
}
else if(n==1)
{
cout<<endl<<n2;
return;
}
fibonacci(n-1,n2,n1+n2);
return;
}
int main()
{
int n;
cout<<"Enter the number:"<<endl;
cin>>n;
fibonacci(n,0,1);
return 0;
}
답변
아직 그 복잡성을 실제로 해결 한 답변이 있는지 잘 모르겠습니다. 시간 복잡도를 변경하지 않고 알고리즘을 더 간단한 알고리즘으로 변환하여 그렇게 할 것입니다. 이것은 둘 다 시간 복잡성을 증명하고 또한 더 쉽게 읽고 추론 할 수있는 알고리즘 버전을 제공합니다.
솔루션부터 시작하겠습니다.
void fibonacci(int n,int n1,int n2)
{
if(n==0)
{
cout<<endl<<n1;
return;
}
else if(n==1)
{
cout<<endl<<n2;
return;
}
fibonacci(n-1,n2,n1+n2);
return;
}
이 else if부분은 실제로 필요하지 않으므로 삭제하고 불필요한 return명령 도 제거하겠습니다 . [이 단계가보기만큼 결백하지 않은 이유에 대한 설명을 참조하십시오.]
void fibonacci(int n,int n1,int n2)
{
if(n==0) {
cout<<endl<<n1; }
else {
fibonacci(n-1,n2,n1+n2); }
}
역 if. 또한 나는 그 중 하나를 다시 넣고 부분 return에서 인쇄를 제거 할 것입니다 else.
void fibonacci(int n,int n1,int n2)
{
if(n!=0) {
fibonacci(n-1,n2,n1+n2);
return ; }
cout<<endl<<n1;
}
꼬리 재귀 최적화를 적용합니다. 즉, 재귀 호출과 다음 반환을 매개 변수의 재 할당 및 서브 루틴 시작으로의 점프로 대체합니다. 이 단계는 공간 복잡성 *을 변경하지만 시간 복잡성은 변경하지 않습니다.
void fibonacci(int n,int n1,int n2)
{
start:
if(n!=0) {
int sum = n1+n2 ;
n1 = n2 ;
n2 = sum ;
n = n-1 ;
goto start ; }
out<<endl<<n1;
}
대신 루프를 사용하십시오 goto.
void fibonacci(int n,int n1,int n2)
{
while(n!=0) {
int sum = n1+n2 ;
n1 = n2 ;
n2 = sum ;
n = n-1 ; }
cout<<endl<<n1;
}
매개 변수가 매개 변수가 될 필요는 없습니다. 나는 아마도 서브 루틴을 문서화 할 것이기 때문에 그것이 무엇을하는지 분명합니다. 그리고 불변으로 while 루프를 문서화하여 작동 방식이 더 명확합니다.
void fibonacci(int n)
// Precondition: n >= 0
// Postcondition: the value of fib(n) has been printed to standard out
// preceded by an end of line.
{
int n1 = 0 ;
int n2 = 1 ;
// Let n0 be the original value if n.
// invariant n1 == fib( n0-n ) and n1 == fib(n0-n+1)
while(n!=0) {
int sum = n1+n2 ;
n1 = n2 ;
n2 = sum ;
n = n-1 ; }
cout<<endl<<n1;
}
(또한 이름이 지정된 장소도 변경하십시오.)
이 시점에서 알고리즘이 O (n)이라는 것이 분명합니다. 어떤 변환도 시간 복잡도를 변경하지 않으므로 원본의 시간 복잡도도 O (n)입니다.
(*) 즉, 컴파일러가 테일 재귀 최적화를 수행하지 않는 한 공간 복잡성을 O (n)에서 O (1)로 변경합니다. 그렇다면 공간 복잡성은 처음부터 O (1)이었습니다.
약 using namespace std
이 문장은 나쁜 습관 으로 간주되므로 피해야합니다 . 가능한 한 피하는 것이 가장 좋습니다. 이유는 다음과 같습니다.
#include <iostream>
#inlcude <list>
using namespace std;
class list // uh-hoh, list is already defined, or is that std::list?
{
...
};
또 다른 문제는 당신이있는 경우이다 어떤 프로젝트의 헤더 파일, 당신은 당신이 헤더를 포함 한 모든 파일이을 강제로 사용하게 될 것이다.
네임 스페이스 std를 사용하는 것이 나쁜 습관으로 간주되는 이유
템플릿 메타 프로그래밍
이렇게하면 계산이 런타임에서 컴파일 타임으로 이동합니다 . 프로그램을 컴파일하는 데 시간이 조금 더 걸리지 만 복잡성은 O(1). 컴파일러가 값을 계산하도록 강제하기 위해 C ++의 템플릿을 사용 합니다.
이것은 계산을 컴파일 시간으로 이동시키기 때문에이 문제에 접근하는 또 다른 옵션이며 가장 빠른 방법 입니다.
그러나 단점은 컴파일 타임에 알려지지 않은 값을 사용할 수 없다는 것입니다. 예를 들어, 5사용자가 입력 할 값 이나 생성 된 임의의 숫자에 대한 값을 찾을 수 있습니다.
#include<iostream>
template <unsigned N>
struct Fibonacci
{
enum : uint64_t
{
value = Fibonacci<N-1>::value + Fibonacci<N-2>::value
};
};
template <>
struct Fibonacci<1>
{
enum
{
value = 1
};
};
template <>
struct Fibonacci<0>
{
enum
{
value = 0
};
};
int main()
{
std::cout << Fibonacci<20>::value;
}
이 방법은 가장 빠르지 만 숫자가 일정한 경우에만 작동합니다.
C ++의 템플릿 메타 프로그래밍
재귀를 반복으로 대체
재귀는 코드를 조금 더 깔끔하게 만들지 만 재귀는 거의 항상 느리게 실행됩니다. 이는 각 호출에 대해 새 스택 프레임을 할당해야하기 때문입니다
. 스택의 공간이 유한 하다는 사실 때문에 재귀 호출 수에 제한이 있습니다. C ++에서 0xC00000FD. 어느 스택 오버 플로우
코드의 몇 가지 더 라인과 함께, 당신은이 시나리오로 재귀를 대체 할 수 있으며이 문제없이, 훨씬 더 빨리합니다.
이것은 재귀를 사용해서는 안된다는 의미는 아니며 일부 알고리즘 에는 재귀 가 필요 하지만 반복으로 대체 할 수 있다면 그만한 가치가 있습니다.
여기에 반복이 있습니다.
uint64_t fibonacci(int n)
{
uint64_t n1 = 0,n2 = 1,n3 = 1;
if (n == 1 || n == 0) return 0;
else if(n == 2) return 1;
for (int i = 2;i < n;++i)
{
n3 = n1 + n2;
n1 = n2;
n2 = n3;
}
return n3;
}
'\n' 위에 std::endl
'\n'그리고 std::endl모두는 당신의 작업을 수행하지만, std::endl호출 std::flush단순히 인쇄보다 속도가 느려집니다 이유는, 모든 시간과 스트림을 플러시'\n'
std :: endl과 '\ n'비교
fib를 작성하는 가장 확실한 방법 :
int fib(int n)
{
if (n < 2) // 0 or 1
{
return 1;
}
return fib(n-1) + fib(n-2);
}
fib ()에 대한 모든 호출에 대해 2 개의 후속 호출이 발생하고 모두 2 회의 호출이 발생하고 모두 2 회의 호출이 발생하기 때문에 폭발하는 것을 볼 수 있습니다.
Level Calls Calls This Level Total Calls
Level n 1 1 1
Level n-1 1 1 2 3
Level n-2 1 1 1 1 4 7
Level n-3 1 1 1 1 1 1 1 1 8 15
그래서 Fib의 복잡성은 Fib !!!!!
더 정확하게는 Complecity는 O(2Fib(n)-1)
상수를 제거하는 것입니다.O(Fib(n))
이를 검증하기위한 코드를 작성해 보겠습니다.
int fibComplexity(int n)
{
// has the same properties of fib.
// but returns the number of calls rather than the value.
if (n < 2)
{
return 1; // You called this function once.
}
return 1 // the call to this function.
+ fibComplexity(n-1) // Count of calls in this tree
+ fibComplexity(n-2) // Count of calls in this tree.
}
이것을 실행하면 :
int main()
{
for(int loop = 2; loop < 15; ++loop)
{
std::cout << loop << " " << fib(loop) << " " << fibComplexity(loop) << "\n";
}
}
생성 : (서식 추가)
n F O
2 2 3
3 3 5
4 5 9
5 8 15
6 13 25
7 21 41
8 34 67
9 55 109
10 89 177
11 144 287
12 233 465
13 377 753
14 610 1219 O = 2f-1
그러나 수강하는 모든 코딩 과정은 선형 기반 솔루션을 만들도록 요청합니다.
위에 제시 한 것은 재귀 적입니다 (그러나 선형 솔루션). 대부분의 사람들은 루프 기반 선형 솔루션을 사용했을 것입니다 (그러나 차이는 없습니다). 복잡성은 정확히 동일합니다.
당신이 한 일은 재귀 적으로 함수를 호출하는 것입니다. 각 호출은 정확히 하나의 추가 호출을 수행하지만 깊이는 n입니다. 그런 다음 돌아옵니다.
그래서 당신은 O(n).
하지만 한 걸음 더 나아갈 수 있습니다. fib 알고리즘은 쉽게 O(1).
이는 fib이 정수의 크기를 빠르게 능가하기 때문입니다. 변수에 저장할 수있는 모든 유효한 값을 쉽게 미리 계산하여 배열에 넣을 수 있습니다. 그런 다음 결과를 조회하여 값을 반환합니다.
int fib(int n) {
static const int fibValue[] = { ... };
if (n < 0 || n > std::size(fibValue)) {
// This is 47 for 32 bit ints
// 93 for 64 bit ints
throw "Result out of range"
}
return fibValue[n];
}
명시 적으로 말하면 : 당신은 \$O(n)\$시간 과 \$O(n)\$기억에. 나는 당신이 정수 산술 (실제로 계산할 때)에서 쉽게 더 잘할 수 있다고 믿지 않지만 메모리는 \$O(1)\$.
Peter Cordes 가 지적했듯이 피보나치 수열에 대한 " 폐쇄 형 "이 있습니다. 즉, 일정한 시간의 무한 정밀도 부동 소수점 시스템을 사용하면 \$O(1)\$. 컴퓨터 부동 소수점은 근사치를 얻을 수 있지만 정수 수학으로 더 정확한 결과를 얻을 수 있다고 생각합니다.
또한 의해 지적 피터 코르 ,는 "이 루카스 시퀀스 방법 할 수있는" \$O(\log{n})\$ 정수 곱셈과 약간 더 복잡합니다.
함수를 반복적으로 사용하여 피보나치 수열을 인쇄하면 시간 결과는 \$O(n^2)\$, 그리고 \ 에서 수행 할 수 있습니다.$O(n)\$.