점화식과 재귀함수, 지수와 로그, 복잡도

□ 점화식

어떤 수열의 일반항을 그 이전의 항들을 이용하여 정의한 식

ex) 피보나치 수열

// 일반적인 방법
    int n = 4; // 4번째 수를 구한다고 가정
    int result = 1;
    for(int i = 0; i< n; i++) {
        if(i == 0) {
            result = 1;
        } else {
            result *= 3;
        }
    }
    
//1, 1, 2, 3, 5, 8, 13, ...의 n번째 수
        int n = 6;
        int result = 0;
        int a1 = 1;
        int a2 = 1;

        if(n < 3) {
            result = 1;
        } else { 
            for(int i = 2; i < n; i++) {
                result = a1 + a2;
                a1 = a2;
                a2 = result;
            }
        }

 

□ 재귀함수

어떤 함수가 자신을 다시 호출하여 작업을 수행하는 방식, 종료 조건이 반드시 존재해야함

static int recursion(int n) {
        if (n == 1) {
            return 1;
        } 
        return 3 * recursion(n-1);
    }
    
static int recursion2(int n) {
        if( n < 3) {
            return 1;
        }

        return recursion2(n-2) + recursion(n-1);
    }

 

 

 

 

 

□ 제곱 : 같은 수를 두 번 곱합

거듭 제곱 : 같은 수를 거듭하여 곱함

제곱근 (=root) : a를 제곱하여 b가 될 때 a를 b의 제곱근이라고 함

Math.pow(2,3);	// 2의 3제곱
Math.sqrt(16);	// 제곱근
Math.abs(-5);	// 절대 값

 

□ 로그 : log a b

a가 b가 되기 위해 제곱해야하는 수

Math.E	// 자연 상수
Math.log(2.71828...)	// 1.0

 

 

 

 

□ 복잡도(Complexity)

알고리즘 성능을 나타내는 척도, 시간 복잡도와 공간 복잡도는 Trade-off 관계

 

 

■ 시간 복잡도

알고리즘의 필요 연산 횟수

- 어떤 문제를 해결하기 위한 알고리즘의 필요 연산 횟수

- 빅오(Big-O) 표기법을 통해 나타냄

O(1) < O(logN) < O(N) < O(N logN) < O(N^2) < O(2^N)

 

■공간 복잡도

알고리즘의 필요 메모리, 요즘은 메모리를 늘려 시간 복잡도를 낮추는 방법을 사용

- 어떤 문제를 해결하기 위한 알고리즘의 필요 메모리 사용량

-  마찬가지로 빅오 표기법을 통해 나타내며 일반적 메모리 사용량 기준은 MB 단위

ex) int[] a = new int[1000]            // 4KB

int[][] a = new int[1000][1000]    // 4MB