[자료구조] 시간복잡도, 빅오표기법

1. 알고리즘 복잡도 분석 (complexity analysis)

(1) 알고리즘을 크게 2가지 측면에서 분석할 수 있다.

    - 시간 복잡도(time complexity) : 수행시간 분석

    - 공간 복잡도(space complexity) : 기억공간 분석

   

(2) 대개 알고리즘의 복잡도를 분석한다는 것은 시간 복잡도를 의미한다.

    시간 복잡도는 알고리즘의 절대적인 시간을 측정하는 것이 아니라

    알고리즘의 연산이 몇 번 수행되는지를 숫자로 표시해 수행 횟수를 비교한다.

 

2. 시간 복잡도(time complexity)

(1) 시간 복잡도 : 프로그램을 실행하여 완료하는데 필요한 컴퓨터 시간의 양

 

(2) T(P) :  컴파일 시간(complie time) + 실행 시간(run time)

    컴파일(compile time)은 한번 성공하면 프로그램을 또 컴파일하지 않고도 실행할 수 있으므로

    시간복잡도에서는 실행 시간(run time)만 신경쓰면 된다.

 

(3) T(n) : 연산의 수를 입력 개수 n의 함수로 나타낸 것 

     연산의 수행횟수는 보통 프로그램에 주어지는 입력 개수 n에 따라 크게 변한다.

     따라서 이에 맞춰 시간복잡도를 구해야 한다.

    

3. 빅오표기법 (Big-O notation)

(1) 일반적으로 자료의 개수가 많은 경우,

      함수의 차수가 가장 큰 항이 가장 큰 영향을 끼치고 나머지 항들은 상대적으로 무시해도 된다.

      예를 들어 T(n) = n^2 + n + 2 이라 할 때,

      상대적으로 n의 값이 크면 클 수록 시간 복잡도에 가장 크게 영향을 미치는 것은 n^2의 항이다.

 

(2) 시간 복잡도 T(n)에서 n에 비례하는 수행시간을 비교해서 알고리즘의 증가 추세를 알고자 할 때

      이것의 시간복잡도를 빅오 표기법 O(n)이라 한다.

      따라서 빅오 표기법으로 입력 개수에 따른 연산의 수행 횟수를 개략적으로 나타내어

      알고리즘의 대략적인 수행시간을 측정할 수 있는 것이다.

 

(3) 빅오 표기법은 함수의 증가에 따라 크게 작용하는 항만 남기고 나머지는 생략하면 된다.

    빅오를 구하는 방법은 기본 연산의 횟수가 다항식으로 표현되었을 때 최고차항의 차수만으로 표현한다.

 

    예를 들어 두 함수가 f(n) = 2n^3+1,

    g(n) = 2n^3 + 5n^2 + 3 라고 할 때

    둘 다 빅오 표기법으로 나타내면 O(n^2)이다.