[피보나치 수열의 일반항 쉽게 구하기] .... x^2=x+1의 두 근을 a, b라 하자. x^n =f(n)x+g(n)에 두 근 a, b를 각각 대입하면 ... a^n=f(n)a+g(n), b^n=f(n)b+g(n) 이 두 식을 빼면... 피보나치수열의 일반항 ... f(n) = {a^n-b^n}/(a-b)
안녕하세요 :) 문제 풀이가 잘 이해가 안가서 댓글 남깁니다. 저는 이 문제를 풀때 트리를 그린 후 각 node들의 runtime (모두 O(n))을 체크하고 후에 노드의 갯수 (2^n)을 곱해서 F(n)의 시간 복잡도(2^n)를 구했고, 이후 allF(n)이 O(n)이 걸린다고 생각해서 n2^n으로 답을 냈는데, 말씀해주신 설명 듣고도 이해가 잘 안가네요!... 실례가 안된다면 다른 접근방법으로 설명 부탁드려도 될까요? 항상 영상 잘 보고갑니다! :D
allF()가 n번 돌면서 2^n의 시간이 걸리는 F()를 호출하는데요, allF()를 자세히보면요, 처음에는 F(1), 그다음에는 F(2),,,그러다가 F(n)까지 호출하자나요? 그래서 이걸 다 합하면 2^1 + 2^2 + ... + 2^(n-1) + 2^n이렇게 되는데요. 맨 마지막 호출 바로 직전까지의 호출한 시간의 총합 즉, 2^1 + 2^2 + ... + 2^(n-1) 얘는요 2^n보다 작아요. (이 앞에 애들이 다 합해도 마지막 호출 한개보다 작다는걸 알아낸사람은 분명 천재일거에요) 그러면 이거 넉넉하게 쳐줘도 2*2^n인거자나요. 근데 BigO에서는 상수는 빼도 되니까,,,그래서 2^n이 되는거에요. 다른 접근방법으로는 딱히 생각이 안나는데요. 한번 고민해볼게요^^
![[자료구조 알고리즘] 빅오표기법 문제풀이](http://i.ytimg.com/vi/QBZnX_P_dj4/mqdefault.jpg)
![[자료구조 알고리즘] 빅오표기법 문제풀이](/img/tr.png)
![[자료구조 알고리즘] 빅오(Big-O)표기법 완전정복](http://i.ytimg.com/vi/6Iq5iMCVsXA/mqdefault.jpg)
아 이누나 -_ -'' 웨케 설명을 잘해...
와 시바 레알.. 강의 영상 다운로드다..~!!!
하나도 모르는 수포자인 내가 들었는데 알 것 같아.. ㅋㅋㅋㅋㅋ
캬~
목소리 넘 이쁘세요~
정말 앵간한 유료 강의보다 유익한 것 같아요..
너무 유익해요
미쳤다리..
뒤늦게 영상을 보면서 공부하고 있는 학생입니다. 혹시 비공개 영상이 뭐였는지 알려주실수 있을가요 공부에 큰 도움이 되고 있습니다
[피보나치 수열의 일반항 쉽게 구하기] .... x^2=x+1의 두 근을 a, b라 하자.
x^n =f(n)x+g(n)에 두 근 a, b를 각각 대입하면 ... a^n=f(n)a+g(n), b^n=f(n)b+g(n)
이 두 식을 빼면... 피보나치수열의 일반항 ... f(n) = {a^n-b^n}/(a-b)
thank you so much
눈나 고마워요
안녕하세요 :) 문제 풀이가 잘 이해가 안가서 댓글 남깁니다.
저는 이 문제를 풀때 트리를 그린 후 각 node들의 runtime (모두 O(n))을 체크하고 후에 노드의 갯수 (2^n)을 곱해서 F(n)의 시간 복잡도(2^n)를 구했고, 이후 allF(n)이 O(n)이 걸린다고 생각해서 n2^n으로 답을 냈는데, 말씀해주신 설명 듣고도 이해가 잘 안가네요!...
실례가 안된다면 다른 접근방법으로 설명 부탁드려도 될까요?
항상 영상 잘 보고갑니다! :D
allF()가 n번 돌면서 2^n의 시간이 걸리는 F()를 호출하는데요, allF()를 자세히보면요, 처음에는 F(1), 그다음에는 F(2),,,그러다가 F(n)까지 호출하자나요? 그래서 이걸 다 합하면 2^1 + 2^2 + ... + 2^(n-1) + 2^n이렇게 되는데요. 맨 마지막 호출 바로 직전까지의 호출한 시간의 총합 즉, 2^1 + 2^2 + ... + 2^(n-1) 얘는요 2^n보다 작아요. (이 앞에 애들이 다 합해도 마지막 호출 한개보다 작다는걸 알아낸사람은 분명 천재일거에요) 그러면 이거 넉넉하게 쳐줘도 2*2^n인거자나요. 근데 BigO에서는 상수는 빼도 되니까,,,그래서 2^n이 되는거에요. 다른 접근방법으로는 딱히 생각이 안나는데요. 한번 고민해볼게요^^
다른 강의 플랫폼에 혹시 올리신거 있나요 돈주고 듣고싶은 강의..
안녕하세요 ㅠㅠ
1:23에
2개씩 n번 증가한다는말은 2xn일수있지않나요?ㅠㅠ...
왜 2^n이 되는지 모르겠습니다 ㅠㅠ
혹시 빅오가 O(n)이 되도록 재귀함수를 사용해서 피보나치 수열을 구현할 수도 있을까요?
ㅠ.ㅠ
double ended queue (deque) 도 부탁드려도 될까요..?