자료구조에 대하여 - 3

_1. BST의 최악의 경우의 예와 시간복잡도에 대해서 설명해주세요.

 

[ 시간 복잡도 ] 

 

표를 보면 

탐색, 삽입, 삭제의

• 평균 시간복잡도 👉 O(logN)
• 최악 시간복잡도 👉 O(N)

 

 

 

 

 

 

 

---

_2. 피보나치 수열을 코드로 구현하는 방법에 대해서 설명해주세요.

 

 

[ 변수 2개 ] 

public static void main(String[] args) {
        int prevPrevNum = 1; // 전 전 항 (n-2)
        int prevNum = 1; // 이전 항 (n-1)

        for (int i = 3; i < 100; i++) {
            int curNum = prevPrevNum + prevNum; // 현재 항 (n)
            System.out.print(curNum + " ");

            prevPrevNum = prevNum;
            prevNum = curNum;
        }
}

 

 

 

[ 배열 ] 

public static void main(String[] args) {
        // STEP 1. 결과값을 담을 배열 선언
        final int[] arr = new int[100];

        // STEP 2. 첫번째 항과 두번쨰 항 미리 선언
        arr[1] = 1;
        arr[2] = 1;
        
        // STEP 3. 반복문을 이용하여, 계속해서 더해 나간다.
        for (int i = 3; i < 100; i++) {
            arr[i] = arr[i - 1] + arr[i - 2];
            System.out.print(arr[i] + " ");
        }
}

 

 

 

[ 재귀함수 ] 

public class Main {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int N = in.nextInt();
 
		System.out.println(fibonacci(N));
 
	}
 
	// 피보나치 함수
	static int fibonacci(int N) {
		if (N <= 1)	return N;
		else return fibonacci(N - 1) + fibonacci(N - 2);
	}
}

 

 

 

 

 

 

---

출처

 

https://mommoo.tistory.com/101

[자료구조] 이진탐색트리

https://memostack.tistory.com/92

피보나치 수열 효율적으로 풀어보기 (Java 알고리즘)

https://st-lab.tistory.com/94

[백준] 10870번 : 피보나치 수 5 - JAVA [자바]