보도에 관하여

함수형 기술 같은 기사를 보고 촉발된 피즈버즈 같은 생각을 하는 절차에서 예전에 피보나치 수열 코드로 동료들과 함께 뜨거워졌다고 생각해 피보나치 수열 코드의 기록을 재고했다.
(본 원고 자체는 함수 유형이 이러쿵저러쿵 말하는 내용이 아니다)

일반적 실현

함수를 되돌려 $n 번째 피보나치 수를 얻습니다.($n=10달러의 예)

fibonacci = lambda n: n if n<2 else fibonacci(n-1) + fibonacci(n-2)
print(fibonacci(10))

동료들은 수열의 결과를 얻고 싶어 하는 것 같아서 수열print(list(map(fibonacci, range(1, 11))))을 얻으면 맵으로 매개 변수열의range 대상을fibonacci로 먹거나 for로 순환한다.
그러나 수열의 상위에서 상하로 계산하는 이 실현이 이뤄지는 상황에서 하위의 피포나치수를 여러 차례 계산해야 하기 때문에 자원을 계산하는 것은 늘 아쉽다.
실제로 $n=40달러 정도면 집행이 늦어진다.
당시 구글을 통해 얻은 결론은 필기화 회귀였지만 전역적으로 배열된 함수 기능의 독립성을 고려해야 한다는 것을 감안하면 나도 저항감이 있었다.(FP의 참조 투명도는 이렇습니까)

하향식

톱다운이 안 되면 톱다운을 하는 게 좋잖아요, 이번에는 다른 답을 쉽게 생각해냈죠.
(큰 범례 변화도 아닌데 그때도 제 생각이 있었어요. 파라미터와 반환값의 처리가 회귀구조에 잘 융합되지 못했기 때문일 거예요.)

fibonacci = lambda n, v=[0,1]: fibonacci(n-1, v+[v[-1]+v[-2]]) if n > 1 else v[1:]
print(fibonacci(10))

이 경우 원래 반환 값은 List 객체에 의해 표시되는 수열이므로 피보나치 수print(fibonacci(10)[-1])를 원하는 경우
Reducter로 쓰면 더 잘 나오지 않을까요?그렇게 생각하지만 원격 프로젝트와 반환 값의 유형이 일치하지 않기 때문에 아무런 변화가 없다.

fibonacci = lambda v, n: v+[v[-1]+v[-2]] if len(v) > 1 else v+[1]
print(reduce(fibonacci, range(1,11), []))

공식 내보내기

계산량에 대해 조사를 진행하였는데, 피보나치 수의 공식이 있는 것 같은데, 아래의 $Fn$n을 풀면 $n의 피보나치 수를 얻을 수 있습니다.
$$
F_n =\frac{1}{\sqrt{5}}\biggl(\;
\Bigl(\frac{1+\sqrt{5}}{2}\Bigr)^n -\Bigl(\frac{1-\sqrt{5}}{2}\Bigr)^n
\biggr)
$$
설치 후 아래와 같습니다.($n 곱하기 루트=$n의 곱하기)

fibonacci = lambda n: int((((1+5**0.5)/2)**n - ((1-5**0.5)/2)**n)/(5**0.5))
print(fibonacci(10))

이렇게 하면 계산 시간은 $O(1)달러인 것 같습니다.1
처음과 마찬가지로 수열의 해를 원한다면 맵으로 range 대상을fibonacci로 먹어라.
하지만 $n=72달러마다 오차가 있습니다..

$ ./fibonacci-bottomup.py 72   # ボトムアップ式実装
498454011879264
$ ./fibonacci-fomula.py 72     # 公式実装
498454011879265

말하자면 이 공식은 수학적으로 정수해를 얻을 수 있을 것 같은데, 어쩔 수 없이 배역을 맡아야 할 때 시행이 틀렸나.

시간 계산량 정보

나 자신은 수학 능력이 없어서 욕을 먹기 쉽다. 수열에 언급된 문장을 찾지 못했지만 $n을 내보낸 피보나치의 시간 계산량은
$$
O_n\Biggl(\quad
\Bigl(\frac{1+\sqrt{5}}{2}\Bigr)^{n-1}
\Biggr)
$$
따라서2 수열판의 시간 계산량은 다음과 같습니까?
$$
O_n\Biggl(\quad
\sum_{i=1}^{n}{\Bigl(\frac{1+\sqrt{5}}{2}\Bigr)^{i-1}}
\;\Biggr)
$$
실수로 보고 싶으므로 명령선 매개 변수로 $n 달러를 수락합니다$n을 획득하는 스크립트를 만듭니다.
fibonacci-sequence-order.py

#!/usr/bin/env python
# -*- coding: utf-8 -*-

import sys

n = int(sys.argv[1])

order = lambda x: ((1+5**0.5)/2)**(x-1)
print(round(sum(list(map(order, range(1,n+1)))),3))

$1\leqn\leq10$에 대한 각각의 $O$n을(를) 내보냅니다.

$ seq 1 10 | xargs -L 1 ./fibonacci-sequence-order.py
1.0
2.618
5.236
9.472
16.326
27.416
45.361
74.395
121.374
197.387

참고 자료

http://www.aoni.waseda.jp/ichiji/2012/java-01/java-14-3.html
http://d.hatena.ne.jp/shunsuk/20090220/1235135606
과거에는 이것에 대해 의문이 있었던 것 같아요. $O(n)$라는 말도 있었지만 $O(1)$로 결정된 것 같은데...?(아래 참조 링크) ↩
간단한 시도?$O(2^n)$↩인 것 같아요.