1. 자료구조와 알고리즘 - (2) 알고리즘의 성능분석

* 알고리즘의 성능 분석

    - 실행 시간이 짧으면서 컴퓨터의 자원들을 적게 사용하는 것이 효율적인 알고리즘
    - 시간 효율성, 공간 효율성

    - 1) 실행 시간을 측정
    - 2) 알고리즘의 복잡도를 분석

 

1. 실행시간 측정

    - 가장 단순하지만 확실한 방법

    - 실행시간 = 종료 시각 – 현재 시각

    - 시각 측정 : C언어에서 clock() 함수
        - 시스템의 현재 시각 반환(CLOCKS_PER_SEC 단위)

-  문제점

    (-) 반드시 구현해야 함
    (-)같은 조건의 하드웨어, 소프트웨어 환경 사용
    (-) 동일한 프로그래밍 언어(컴파일 방식 / 인터프리터 방식)
    (-) 성능 평가를 한 데이터에 대해서만 유효

 

2. 알고리즘의 복잡도 분석

    - 구현하지 않고 알고리즘의 효율성 평가하는 방법

    - 처리시간을 직접 측정하는 대신 알고리즘의 연산횟수를 대략적으로 계산
        - 대입, 사칙연산 다 각각 1으로 보고, 줄 별로 횟수 더함… 반복되면 n곱해서 더함

* 복잡도의 점근적 표기
    : 복잡도 함수를 최고차항만 계수 없이 취해 단순하게 표현

[1] 빅 오

    : O(g(n)) = 증가 속도가 g(n) 과 같거나 낮은 모든 복잡도 함수를 모두 포함
        //복잡도 함수가 2n + 1 이면, 이 알고리즘은 O(n) 에 속함, O(n)이다
        //2n + 1 의 증가 속도가 n과 같기 때문

    - 어떤 경우에도 n에 비례하는 시간 내에는 반드시 완료된다는 뜻임

    - O(n^2)에는 2n – 3 이것도 포함됨. 2n-3의 증가 속도는 n^2보다 느리기 때문

    - 빅오 = 처리시간의 상한, upperbound

    1 < log n < n(<- 선형시간… n에 비례하는 시간 걸림) < n log n < n^2 < n^3 < 2^n < 3^n < n!

[2] 빅 오메가

    : Ω(g(n)) = 증가 속도가 g(n)과 같거나 높은 모든 복잡도 함수 = 복잡도 함수의 하한 = lowerbound

    - Ω(g(n^2)) = 아무리 빨리 처리하더라도 n^2 이상의 시간은 반드시 걸린다
        = n^3도 Ω(n^2)에 포함됨

[3] 빅 세타

    : Θ(g(n)) = 증가 속도가 g(n)과 같은 복잡도 함수들만을 포함함 = 상한인 동시에 하한인 경우
        = 시간 복잡도를 정확히 계산할 수 있다면 세타를 사용,
            정확히 분석하기 어렵다면 상한을 구해 빅 오 표기법으로 나타내거나 하한을 구해 빅 오메가로

    //일반적으로는 최악의 상황을 고려한 해결책 찾기 때문에 빅 오 표기법을 주로 사용함