알고리듬 효율성 기초자료구조(1)

알고리듬

---

어떤 문제를 해결하는 명백한 방법
Building Block 하여 변화되어 재생성 되는 알고리듬에 기본 유형을 파악하고 문제 해결

효율성

---

자원(resource)의 효율적 사용을 뜻한다
시간 : CPU 속도 등..
공간/용량 : 메모리 사용량 등
시간과 공간은 종종 상반 관계인데 시간을 적게 사용하면 공간을 그만큼 더 사용 반대일 경우도 마찬가지
자원을 많이 사용하면 알고리듬이 복잡하다고 말한다

시간 복잡도

---

O(1)

public class Calculator {
    public int add(int num1, int num2) {
        return num1 + num2; // 한번의 연산
    }
}

O(n)

public class Calculator {
    public int add(int num1, int num2) {
        int sum = num1;
        for (int i = 0; i < num2; ++i) {
            ++sum; // 0 부터 num2 만큼 cpu 연산
        }
        return sum;
    }
}

공간 복잡도

---

O(1)

public class SpaceComplexity {
    public int getFactorial(int n) {
        int i = 0;
        int result = 1;
        for (i = 1; i <= n; i++)
        {
            result = result * i;
        }
        return result;
    }
}

O(n) 재귀함수로 스택에 n ~ 1 까지 쌓인다

public class SpaceComplexity {
    public int getFactorial(int n) {
        if (n > 1) return n * getFactorial(n - 1);
        else return 1;
    }
}

점근 표기법(asymptotic notation)

---

점(점) 가까울(근)
어떤 함수가 증가하는 모습을 다른 함수와 비교
알고리듬의 복잡도를 논하거나 단순화할 때 사용

빅오 표기법 (대문자 O 표기법)

---

알고리듬을 분류하기 위해 사용
표기법 크기 [작음]O(1) O(log n) O(n) O(nlog n) O(n2) O(2n) O(n!)[큼]
O 의 의미 : order of the function (대략 그 함수 정도) 너무 디테일하게 정하지 말자는 의미에서 사용
2n = 2배씩 증가 log2n = 절반씩 줄여나가는, 이진트리검색 생각하면 된다 가운데로 접근하여 해당사항이 없는곳은 버리는 방식
log 관련해서는 정렬 알고리즘 공부할 때 자세히 보게 될 예정
입력 데이터가 많아짐에 따라 실행 시간(시간 복잡도), 필요한 공간(공간 복잡도)이 얼마나 늘어나는지 측정

참고사항

---

실행 복잡도가 O(n2) 이상 O(n3 ...), O(2n), O(n!) 많이 느리므로 고려해봐야 한다

master's theorem(마스터 정리)

간단하고 빠른 방법으로 반복 관계(분석 정복 알고리즘)의 시간 복잡도를 계산하는 데 사용
궁금하면 검색해서 한번 구경해보라는 김포프센세의 말씀 메모..