2021-07-02 알고리즘 분석과 차수

■ 알고리즘의 분석

   □ 정확성 분석: 모든 입력 사례에 대해서 정확한 해답을 찾는다는 것을 증명

   □ 효율성 분석: 입력 크기가 커지는 정도에 따라 성능의 변화량을 증명

        - 시간 복잡도: 시간을 기준으로 알고리즘의 효율성 분석

        - 공간 복잡도: 공간을 기준으로 알고리즘의 효율성 분석

 

■ 알고리즘의 성능 분석

   □ 퍼포먼스 측정: 실행 시간을 직접 측정하거나 실행 명령의 숫자 세기

        - 컴퓨터의 성능이나 프로그래밍 언어에 따라 달라짐

   □ 복잡도 분석: 컴퓨터나 프로그래밍 언어와 무관하게 성능 분석

        - 입력 크기에 따른 단위 연산의 실행 횟수 세기

 

■ 복잡도 분석

   □ 입력 크기: 문제가 가진 파라미터, 즉, 입력 사례의 크기

   □ 단위 연산: 알고리즘 실행의 기본이 되는 명령어들의 집합

 

■ 알고리즘의 시간 비교

   □ 시간 복잡도: 입력크기(n)에 대한 단위 연산 횟수의 함수 f(n)

   □ 시간 복잡도가 f1(n) = n인 알고리즘과 f2(n) = n^2인 알고리즘

   □ 만약 단위 연산의 실행시간이 f1은 1000t, f2는 t라면?

       - f1 알고리즘 전체 실행 시간: n x 1000t

       - f2 알고리즘 전체 실행 시간:n^2 x t

       - n>1000 일때 f1이 f2보다 궁극적으로 더 빠르다고 할 수 있다.

 

■ 차수(Order): 알고리즘의 궁극적인 성능 분류

   □ 시간 복잡도 함수의 차수로 알고리즘의 성능을 분류할 수 있다.

   □ 모든 n차 시간 알고리즘은 궁극적으로 n+1차 시간 알고리즘보다 빠르다.(낮은 차수의 항들은 버릴 수 있음)

   □ 상수시간, 로그시간, 선형시간, 선형로그시간, 2차시간, 3차시간, 지수시간, 팩토리얼 시간

   □ 점근적 표기법:

       - Big O(복잡도 함수의 점근적 상한)

       - 오메가(복잡도 함수의 점근적 하한)

       - 세타 ( Big O + 오메가)