[TIL]200908 복잡도분석(Complexity Analysis)

Chaegyeom·2020년 9월 8일
0

TIL

목록 보기
29/77
post-thumbnail

알고리즘이란?

알고리즘이란 어떤 일을 하는 절차를 말한다. 컴퓨터에서는 프로그램이 수행할 작업(명령의 집합)이다.

그렇다면 알고리즘이라면 가져야할 조건은 어떤 것이 있을까? 조건은 다음과 같다.

  1. 입력이 있다.(0이상의 입력)
  2. 출력이 있다.(최소 한개의 출력)
  3. 명확해야 한다.
  4. 유한성(한정된 수의 절차 후에 종료되어야 함)

알고리즘은 3가지 기능(순서, 반복, 조건)으로 서술된다.

  • 순서(sequence) : 명령어 다음에 명령어가 나온다.
  • 반복(repetition) : 명령어가 반복 된다.
  • 조건(condition) : 조건에 따라 명령의 수행이 결정된다.

알고리즘이란 작업을 수행하는 것이기 때문에 성능(효율성)이 있는데, 오늘은 성능분석 중에서 시간복잡도에 대한 내용을 배웠다.

알고리즘의 성능(performance)

알고리즘의 성능(performance)의 분석은 컴퓨터에 상관없이 시간과 공간의 추산에 초점을 두고 분석하는데 그 중 시간복잡도(Time Complexity)는 프로그램을 실행시켜 완료하는 데 걸리는 시간인데 프로그램에 의하여 실행되는 시간은 컴퓨터의 성능에 따라 달라질 수 밖에 없다. 따라서 절대적인 시간보다는 연산의 개수를 통해 분석한다.

알고리즘의 수행시간 비교는 입력데이터 개수(n)에 대한 함수로 결정된다. 이는 같은 작업을 시켰을 때 어느 알고리즘이 빠른가? 와 같다.

시간 복잡도(time complexity)를 결정하는 요소는 아래와 같다.

  1. 입력의 크기(input size) : 입력되는 데이터 n의 크기
  2. 입력 데이터의 형태
    • 입력 가능한 형태에 따라 평균시간최악의경우가 있다.

보통 시간복잡도에서 최악의 경우에 관심을 갖는데, 최악의 경우는 상한시간이 관심대상이다.

그렇다면 이렇게 분석해서 어떻게 표현할 수 있을까?

O표기법

O표기법이 있는데 이것은 알고리즘의 수행시간을 기본이 되는 명령어가 입력데이터 n에 대하여 수행되는 횟수로 나타내는 것인데 알고리즘을 비교할 때 수행시간을 직접재서 비교하는 것이 아닌 입력 데이터의 갯수(n)에 대한 함수로 결정하는 것이다. O표기법에 대한 증명이 있는데 증명을 하기에는 지금 내가 배워야 할 것들이 너무나 많다.

빅-오표기법(big-O)

내가 배운 방법은 빅오(big-O)표기법이다.
빅-오(big-O)표기법 : 연산의 횟수를 대략적(점근적)으로 표기한 것
유사한 다른 표기법으로는 Big-Ω(빅오메가), Big-Θ(빅세타)가 있다.

  • big-O: 알고리즘의 최악의 상태를 표기(가장 느린 경우)
  • big-Ω: 알고리즘의 최상의 상태를 표기(가장 빠른 경우)
  • big-Θ: 알고리즘의 평균의 상태를 표기(중간)
    알고리즘 측정 시 최악의 상태보다 빠르다는 것이 확실히 보장므로 big-O표기법을 많이 사용한다.

자료의 갯수가 많은 경우에는 차수가 가장 큰 항이 가장 큰 영향을 미치고 다른 항들은 상대적으로 무시될 수 있다. 예를 들면 n이 10000일때 T(n) = n^2 + n + 1 이라면 100010001이라는 값이 나오는데 n^2의 값인 100000000은 전체 계산인 T(n)중 차지하는 비율이 99.9900000001 %이다 나머지 n+1의 값인 1001은 0.0099999999 %의 비율을 차지하는데 보통 시간복잡도 함수에서 가장 영향을 크게 미치는 항만을 고려해도 충분하다고 생각한다.

big-O표기법에서 시간복잡도를 표기하는 표기법 및 종류

O(1): 상수형
O(logN): 로그형
O(N): 선형
O(N logN): 선형 로그
O(N²): 제곱
O(N³): 세제곱
O(2ⁿ): 2의 n 제곱
O(N!): 팩토리얼
이 있고 그래프로 나타내면 아래와 같다

측정방법

측정방법은 알고리즘에서 코드가 몇 번 실행되는지 측정한 후, 상수는 1로 표시하고, 지수는 가장 큰 차수만 표시한다.

profile
주니어 개발자가 되고싶은

0개의 댓글