1. 시간복잡도 (영리한 프로그래밍을 위한 알고리즘 강좌)

1. 시간복잡도(time complexity)란?

 - 알고리즘의 자원(resource) 사용량을 분석

 - 자원이란 실행 시간, 메모리, 저장장치, 통신 등

 

1-1 실행시간

 - 실행시간은 실행환경에 따라 달라짐 ex) 하드웨어, 운영체제, 언어, 컴파일러 등

 - 실행 시간을 측정하는 대신 연산의 실행 횟수를 카운트 (같은 조건에서 연산의 실행 횟수를 본다는 의미)

 - 연산의 실행 횟수는 입력 데이터의 크기에 관한 함수로 표현 (ex O(n))

 - 데이터의 크기가 같더라도 실제 데이터에 따라서 달라짐

 - worst-case analysis 최악의 경우 시간 복잡도, average-case analysis 평균 시간복잡도

 

1-2 점근적(Asymptotic) 분석

 - 점근적 표기법을 사용 : 데이터의 개수가 n -> 무한대일때 수행시간이 증가하는 growth rate로 시간복잡도를 표현 하는 기법. Θ-표기, Ο-표기 등을 사용

 - 다른 분석법에 비해 상대적으로 가장 간단하며, 알고리즘의 실행환경에 비의존적이기 때문에 가장 광범위하게 사용됨.

 

1) 상수 시간 복잡도

 - n에 관계없이 상수 시간이 소요된다. 이 경우 알고리즘의 시간복잡도는 O(1)이다.

 - 입력으로 n개의 데이터가 저장된 배열 data가 주어지고, 그 중 n/2번째 데이터를 반환한다. 

int sample(int data[], int n){
	int k = n / 2;
	return data[k];
}

 

2) 선형 시간복잡도  

 - 선형 시간복잡도를 가진다고 말하고 O(n)이라고 표기한다.

 - 입력으로 n개의 데이터가 저장된 배열 data가 주어지고, 그 배열 요소의 합을 구하여 반환한다.

int sum(int data[], int n){
  int sum = 0;
  for (int i = 0; i < n; i++)
    sum = sum + data[i];
  return sum;
}
    

 - sum = sum + data[i]; 

 -> 이 알고리즘에서 가장 자주 실행되는 문장이며, 실행 횟수는 항상 n번이다. 가장 자주 실행되는 문장의 실행 횟수가 n번이라면 모든 문장의 실행 횟수의 합은 n에 선형적으로 비례하며, 모든 연산들의 실행횟수의 합도 역시 n에 선형적으로 비례한다.

 

2-1) 선형 시간복잡도 : 순차탐색

 - 배열 data에 정수 target이 있는지 검색한 후 target값에 해당하는 index를 반환한다.

 - 최악의 경우 시간복잡도는 O(n)이다.

 

int search(int n, int data[], int target){
  for (int i = 0; i < n; i++){
    if (data[i] == target)
      return i;
  }
  return -1;
}

 

 - if (data[i] == target)

  -> 이 알고리즘에서 가장 자주 실행되는 문장이며, 실행 횟수는 최악의 경우 n번이다.

   

3) Quadratic

 - 배열 x에 중복된 원소가 있는지 검사하는 함수. 중복된 요소가 있으면 false리턴

 - 최악의 경우 배열에 저장된 모든 원소 쌍을 비교 하므로 비교 연산의 횟수는 n(n-1)/2이다. 최악의 경우 시간복잡도는 O(n²)으로 나타낸다.

bool is_distinct(int n, int x[]){
  for (int i = 0; i < n - 1; i++)
    for (int j = i + 1; j < n; j++)
      if (x[i] == x[j])
        return false;
  return true;
}

 - if(x[i]==x[j])

  -> 이 알고리즘에서 가장 자주 실행되는 문장이며, 최악의 경우 실행 횟수는 n(n-1)/2번이다.

 

for (i = 1; i < n; i* = 2){ 
  // Do something <- 이 문장의 실행 횟수는?
}

 

1-3 점근적 표기법

 - 알고리즘에 포함된 연산들의 실행 횟수를 표기하는 하나의 기법

 - 최고차항의 차수만으로 표시

 - 따라서 가장 자주 실행되는 연산 혹은 문장의 실행횟수를 고려하는 것으로 충분

 

*점근적 표기법의 추가적인 자료는 

인프런 - 영리한 프로그래밍을 위한 알고리즘 강좌에서 첨부한 PDF로 대체

https://s3.ap-northeast-2.amazonaws.com/inflearnattachment/algorithm/chap01_time_complexity.pdf