피보나치 수열 합/시간 계산 알고리즘

def fibonacci(n):

    answer = [0,1]    #list의 초기값을 0,1로 지정

 

    for i in range(2,n+1):#i= list의 주소를 뜻함

        answer.append(answer[i-1]+answer[i-2])#list에 추가

    #print(answer)  # 피보나치 list를 출력위해

    #print(i)       #리스트 주소가 잘 돌고있는지 확인

    return answer[-1]    #리스트에서 가장 마지막것만 출력해줌

 

$print(fibonacci(30))

832040

초기에 python으로 해결하려 하였으나 실패ㅜㅜ 시간 계산 함수가 따로있다고 하는데 조금 더 찾아보고싶었지만 노타임.. 노열정..

 

<python 으로 반복문 사용하여 피보나치 계산> -> 아 잘되는데 시간 계산 .....

<java 피보나치 합 /시간 계산>

 

import java.util.Scanner;
 
public class recursionVsIteration {
 
    public static void main(String[] args) {
 
        Scanner sc = new Scanner(System.in);
 
        //원하는 숫자 입력
 
        System.out.print("Enter the last element of Fibonacci sequence: ");
 
        long n = sc.nextInt();
 
        //반복문 출력
 
        System.out.println("Fibonacci iteration:");
 
        long start = System.currentTimeMillis();
 
        System.out.printf("Fibonacci sequence(element at index %d) = %d \n", n, fibIteration(n));
 
        System.out.printf("Time: %d ms\n", System.currentTimeMillis() - start);
 
        //재귀함수 출력
 
        System.out.println("Fibonacci recursion:");
 
        start = System.currentTimeMillis();
 
        System.out.printf("Fibonacci sequence(element at index %d) = %d \n", n, fibRecursion(n));
 
        System.out.printf("Time: %d ms\n", System.currentTimeMillis() - start);
 
    }
 
    //반복문 method
 
    static long fibIteration(long n) {
 
        long x = 0, y = 1, z = 1;
 
        for (long i = 0; i < n; i++) {
 
            x = y;
 
            y = z;
 
            z = x + y;
 
        }
 
        return x;
 
    }
 
    //재귀 method
 
    static long fibRecursion(long  n) {
 
        if ((n == 1) || (n == 0)) {
 
            return n;
 
        }
 
        return fibRecursion(n - 1) + fi

 

 

 

---

<피보나치 수열>

1	0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...

 

 

<피보나치 수열의 호출 방법>

1. 재귀 호출 

-함수 호출 횟수가 너무 큼                                                     -> 해결책 : recursive를 한겹만 쓰면 확실히 줄어들 것

-stack 깊이가 너무 깊어져서 컴퓨터 터짐..(stack overhead)-> 해결책 : stack을 쓰되 새로 만들지말고 누적해서 재사용하자

 

-대신 적은 코드 사용해 효율적으로 처리                              -> 종료하는 지점 정의해줬을 때 얘기이다..

 

2. 반복 호출 

- 반복 할 때마다 나온 계산 값을 어딘가에 저장해 두고 그 다음 반복에서는 앞 단계에서 저장된 값에 새로운 값 내용 누적 시킨다.

- 매개변수 리스트 보관(메모리 영역) / 메소드 실행공간(복사 공간) 필요하다

 

3. 꼬리 재귀(tail-recursion)

-재귀가 느려지는 이유(작업 끝마쳐도 해야할 일 남아)를 보완해서 함수의 꼬리 부분에 호출하여 원래 시점으로 돌아갔을 때 해야할 일 이 없게 만드는 호출

 

---

 

-참고 블로그 : https://nittaku.tistory.com/81