복잡도

프로그램의 실행 속도는 프로그램이 동작하는 하드웨어나 컴파일러 등의 조건에 따라 달라진다.
알고리즘의 성능을 객관적으로 평가하는 기준을 복잡도(complexity)라고 한다.
복잡도는 두 가지 요소를 가지고 있다.

1. 시간 복잡도 (space complexity) : 실행에 필요한 시간을 평가한 것
2. 공간 복잡도 (space complexity) : 기억 영역과 파일 공간이 얼마나 필요한가를 평가한 것

선형 검색과 이진 검색의 시간 복잡도에 대해 공부해보자.

선형 검색의 시간 복잡도

// 예시 메소드
static int seqSearch(int[] a, int n, int key){
  int i = 0; // 실행 횟수 1회 = 복잡도 O(1)
    
  while(i < n) { // 실행 횟수 n/2회 = 복잡도 O(n)
    if(a[i] == key)  // 실행 횟수 n/2회 = 복잡도 O(n)
      return i;  // 실행 횟수 1회 = 복잡도 O(1)
    i++;  // 실행 횟수 n/2회 = 복잡도 O(n)
  }
  return -1;  // 실행 횟수 1회 = 복잡도 O(1)
}

int i = 0;
return i;
return -1;

변수 선언 및 초기화나 값을 반환하는 return의 경우 1번만 실행되기 때문에 O(1)이라고 표기한다.

while(i < n) {
if(a[i] == key)
i++;

위 세가지는 n에 비례하는 횟수만큼 실행하기 때문에 복잡도를 O(n)으로 표기한다.
여기서 복잡도를 O(n/2)로 표기하지 않는 이유는,
컴퓨터에서 n/2와 n의 차이는 크지 않아 무의미하다.
100번을 실행하는 경우에도 O(100)이 아닌 O(1)로 표기한다.

2개 이상의 메소드는 아래와 같은 특징을 가진다
ex) max(a,b)는 a와 b 가운데 큰 쪽을 나타내는 메소드이다.

O(f(n))+O(g(n)) = O(max(f(n),g(n)))

O(1)+O(n)+O(n)+O(1)+O(n)+O(1)=O(max(1,n,n,1,n,1)) = O(n)

2개 이상의 복잡도로 구성된 알고리즘의 전체 복잡도는 차수가 더 높은 쪽의 복잡도가 지배한다. 둘 뿐만 아니라 셋 이상의 계산으로 구성된 알고리즘도 마찬가지이다.
다시 말해 전체 복잡도는 차수가 가장 높은 복잡도를 선택한다.