시간 복잡도

시간복잡도란 알고리즘이 문제를 해결하기 위한 시간(연산)의 횟수를 말합니다.

 

알고리즘을 평가하는데 있어 수행시간과 메모리 사용량을 평가기준으로 두는데 

수행시간에 해당하는 것이 시간 복잡도(Time Complexity)

메모리 사용량에 해당하는 것이 공간 복잡도(Space Complexity)입니다.

 

연산 횟수를 카운팅할 때 3가지 경우가 있습니다.

1. 최선의 경우 Best Case
2. 최악의 경우 Worst Case
3. 평균적인 경우 Average Case

평균적인 경우가 가장 이상적으로 보이겟지만 알고리즘이 복잡해 질수록 평균적인 경우는 구하기가 매우 어렵습니다.

그러므로 최악의 경우로 알고리즘의 성능을 파악합니다.

 

Program Step에서 Elementary Operation

프로그램의 진행 정도를 나타내는 기본단위

1. 대입연산
2. 덧셈, 뺄셈, 곱셈, 나눗셈
3. 비교구문
4. 함수호출

즉, 알고리즘의 실행 순서를 따라가며 Elementart Operation이 일어나는 수를 측정 

1. 전역변수를 이용한 Elementary Operation 카운팅
2. 각 실행문 별로 Step수와 실행 횟수를 분석

전역변수를 이용하여 Elementary Operation을 카운팅

<script>
 let count = 0; 
    
 function sum(list, n){
  let tempSum = 0; //대입연산
  for(let i = 0; i<n; i++){
   count++; // loop 한번 돌 때마다
   tempSum += list[i]; 
   count++; // 대입연산
  }
  count++; //for loop 끝날 때 한번
  count++; //return 수행
  return tempSum;
 }
</script>

 

각 실행문 별로 Step수와 실행 횟수를 분석

주어진 프로그램 2개의 성능 비교 및 분석

 

 

문제를 해결하려고 할 때마다 시간 복잡도를 분석하는 습관을 들이면 좋은 개발자가 될 수 있습니다.

엔지니어에게 있어서, 문제라는 것은 정답이나 최선의 답의 관점에서 접근하는 것보다, 상황에 더 맞는 답인지 아닌지의 관점에서 접근해야 합니다.

 

Big-O 표기란?

O(1) - 상수 시간 : 입력 값 n이 주어졌을 때, 알고리즘이 문제를 해결하는데 오직 한 단계만 거칩니다.

O(log n) - 로그 시간 : 입력 값 n이 주어졌을 때, 문제를 해결하는 데 필요한 단계들이 연산마다 특정요인에 의해 줄어듭니다.

O(n) - 직선적 시간 : 문제를 해결하기 위한 단계의 수는 입력 값 n의 제곱입니다.

O(n^2) - 2차 시간 : 문제를 해결하기 위한 단계의 수는 입력값 n의 제곱입니다.

O(C^n) - 지수 시간 : 문제를 해결하기 위한 단계의 수는 주어진 상수값 C의 n 제곱입니다.