Time Complexity

시간 복잡도

입력값의 증감에 따라 시간이 얼마만큼 비례하여 증감하는가? 즉, 입력값이 커짐에 따라 증가하는 시간의 비율을 얼마나 최소화하였는가와 동일. "이 정도 시간까지 걸릴 수 있다"

표기 방법은 Big-O (최악의 경우), Big-Ω (최선/최적의 경우), Big-θ (평균)

1. Big-O

• O(1): constant complexity, 입력값의 크기와 상관없이 즉시 출력값을 얻을 수 있음. 하기 알고리즘에서는 전달인자의 값이 얼마나 큰 지 상관없이 즉시 값을 얻을 수 있음.

function sasha(arr, idx){
	return arr[idx];
}
let arr = [1,2,3]
let idx = 2
let result = sasha(arr,2);
console.log(result);

• O(n): linear complexity, 입력값이 증가함에 따라 시간 또한 같은 비율로 증가함. 입력값이 커질수록 계수값의 영향이 점점 적어지기 때문에, 같은 비율로 증가하고 있더라도 O(n)으로 표기.

function sasha(n){
for(let i = 0; i < n; i++){
return i;
}
}

function sasha2(n){
for(let i = 0; i < 2n; i++){
return i;
}
}// 코드의 실행 시간이 2초씩 증가. 

• O(log n): logarithmic complexity, O(1) 다음으로 빠른 시간 복잡도를 가짐. 대표적인 예인 BST의 경우, 원하는 값을 탐색할 때, 노드를 이동할 때마다 수가 절반으로 줄어들어, 후반으로 갈 수록 연산해야 할 양이 적어짐.

• O(n log n): 합병 정렬.

• O(n^2): quadratic complexity, 입력값이 증가함에 따라 시간이 그의 제곱의 비율로 증가하는 것을 의미. 하기 코드에서 loop 안에 loop가 계속 추가될 때마다 연산에 걸리는 시간은 곱으로 증가함을 알 수 있음.

function sasha(n) {
  for (let i = 0; i < n; i++) {
	for (let j = 0; j < n; j++){
      ...
    }
  }
}

• O(2^n): exponential complexity, Big-O 표기법 중 가장 느린 시간 복잡도를 가짐. 구현한 알고리즘의 시간 복잡도가 해당과 같다면, 다른 접근 방식을 고려해 볼 것.

function fibonacci(n) {
  if (n<=1){
  return 1;
  }
  return fibonacci(n-1) + fibonacci(n-2);
}

---

프로그램 작성 시, 정확한 값을 제한된 시간 내에 반환하는 프로그램을 작성해야함. 시간 제한과 주어진 데이터 크기 제한에 따른 시간 복잡도를 대략적이나마 예측해보는 것이 중요.

데이터 크기 제한	예상되는 시간 복잡도
n <= 1,000,000	O(n) or O(log n)
n <= 10,000	O(n^2)
n <= 500	O(n^3)

Dynamic programmimg

동적 계획법, 주어진 문제를 여러 개의 하위 문제로 나누어 풀고, 하위 문제들의 해결 방법을 결합하여 최종 문제를 해결하는 문제 해결 방식. 하위 문제를 계산한 뒤 그 해결책을 저장(Memoization)하여, 후에 같은 하위 문제가 나왔을 경우 저장된 해결책을 이용하여, 계산 횟수를 줄임.

본 프로그래밍은 다음과 같이 두 가지 가정이 만족하는 조건에서 사용 가능.

• 큰 문제를 작은 문제로 나눌 수 있고, 이 작은 문제들은 중복된다. (Overlapping Sub-problems)
• 작은 문제에서 구한 정답을 큰 문제에서도 사용 가능 (Optimal Substructure)