[알고리즘] 알고리즘 분석 개요

학교에서 들은 알고리즘 분석 강의 내용을 복습하면서 작성한 글입니다.
March 12, 2024 4:29 PM

Algorithm

• Definiteness - clear and unambigiuous
• Finiteness - 크고 길 수는 있지만 terminate 해야함
• Effectiveness - 간단하고, 구현가능해야함

P-NP 문제

Deterministic (P)	Non-deterministic (NP)
-deterministic polynomial time : 다항 시간 내에 yes-no 대답 가능 예: 3n^3+2n^2+7n+2 다항 시간 내에 해결할 수 있는 결정 문제	-쉽게 해결할 수 있는 비결정적 결정 문제들의 집합 -여러 가지 풀이 가능성을 고려할 수 있음 다항 시간 내에 검산할 수 있는 문제 둘은 상호 배타적인 관계가 아니다!!!!!!

 

Fibonacci term

• recursive: T(n) > 2^{n/2} → bad
• iterative → much more effective
• 각각의 알고리즘, 시간복잡도

recursion (간단하지만 중복계산이 많음)

int fib(int n) 
{ 
    if (n <= 1) 
        return n; 
   else 
        return fib(n-1) + fib(n-2); 
}

이에 따른 시간복잡도 O(n^2)

iteration (Dynamic Programming)

int fib(int n)
{
    index i;
    int f[0...n];  //n까지의 피보나치 수열을 저장할 배열
    f[0]=0;  //첫 번째 피보나치 수는 0
    if(n>0){
        f[1] = 1;  //두 번째 피보나치 수는 1
        for (i=2; i<=n; i++)  //i가 n이 될 때까지 반복
            f[i] = f[i-1] + f[i-2];  //이전 두수의 합이 현재의 수
        }
        return f[n]; //n번 째 피보나치 수를 반환
}

이에 따른 시간복잡도 O(n)

Time Complexity Analysis

• Efficiency 판단: 다른 외부 요건은 배제, input size에 대한 function 실행시 basic operation의 number
• 때로는 input size 말고도 input value에 영향을 받기도 한다.
• T(n) = every case 가 존재하면 T(n) = W(n) = A (n) = B(n), 존재하지 않으면 W(n), A(n)

Space Complexity Analysis

Fixed Part

-명령어 공간

-static variable

-constants

-고정 된 배열 등

 

Variable Part

-가변 변수

-recursion stack(실제 시스템에서 사용하는 space)

recursion 보단 iteration 선호 : stack 안 쌓임