시간복잡도

효율적인 알고리즘을 구현한다는 것은,
입력값이 커짐에 따라 증가하는 시간의 비율을 최소화한 알고리즘을 구성했다는 것...

1. 시간복잡도

• 입력값의 변화에 따라 연산을 실행할 때, 연산 횟수에 비해 시간이 얼마나 걸리는지 표현한 것
  시간 복잡도를 표기하는 방법

  1. Big-O (빅-오) : 상한 점근(최악)
  2. Big-Ω (빅-오메가) : 하한 점근(최선)
  3. Big-θ (빅-세타) : 평균(중간)

• 이 중에서 Big-O 표기법이 가장 자주 사용된다. 빅오 표기법은 최악의 경우를 고려하므로, 프로그램이 실행되는 과정에서 소요되는 최악의 시간까지 고려할 수 있기 때문이다.

• 빅오는 입력값의 변화에 따라 연산을 실행할 때, 연산 횟수에 비해 시간이 얼마나 걸리는지 표기하는 방법이다.

1. O(1)

• O(1)은 constant complexity라고 하며, 입력값이 증가하더라도 시간이 늘지 않는다. 즉, 입력값의 크기와 상관없이, 즉시 출력값을 얻어 낼 수 있다는 의미이다.
  예) array의 index 값 찾기

2. O(n)

• O(n)은 linear complexity라고 부르며, 입력값이 증가함에 따라 시간 또한 같은 비율로 증가하는 것을 의미한다.
• 예를 들어 입력값이 1일때 1초의 시간이 걸리고, 입력값을 100배로 증가시켰을 때 1초의 100배인 100초가 걸리는 알고리즘을 구현했다면, 그 알고리즘은 O(n)의 시간 복잡도를 가진다고 할 수 있다.
  예) 1개 for문에서 배열 탐색

3. O(log n)

• O(log n)은 logarithmic complexity라고 부르며 Big-O 표기법 중 O(1) 다음으로 빠른 시간 복잡도를 가진다.
• n이 주어졌을 때 계속해서 1/2 씩 줄어들기 때문에 연산 횟수는 log2(n) 이면, Big-O 표기법으로 나타내면 log n 이다.
  예) Binary Search Tree

4. O(n^2)

• O(n^2)은 quadratic complexity라고 부르며, 입력값이 증가함에 따라 시간이 n의 제곱수의 비율로 증가하는 것을 의미한다.
• 예를들어 입력값이 1일 경우 1초가 걸리던 알고리즘에 5라는 값을 주었더니 25초가 걸리게 된다면, 이 알고리즘의 시간복잡도는 O(n^2)라고 표현한다.
• n^3과 n^5도 모두 O(n^2)로 표기한다. n이 커지면 커질수록 지수가 주는 영량력이 점점 퇴색되기 때문에 이렇게 표기한다.
  예) 2개의 중첩 for문, 3개의 중첩 for문

5. O(2^n)

• O(2^n)은 exponential complexity라고 부르며 Big-O 표기법 중 가장 느린 시간 복잡도를 가진다.
  예) 재귀로 구현하는 피보나치 수열

대략적인 데이터 크기에 따른 시간 복잡도

예시 문제

• Q. 다음의 시간 복잡도를 가지는 알고리즘이 있을 때, 가장 느린것과 가장 빠른것은?
  • O(n)
  • O(2^n)
  • O(log n)
  • O(n^2)
  • O(n!)
• A. 가장 빠른것- O(log n)/ 가장 느린것 - O(n!)

2. Greedy Algorithm(탐욕 알고리즘)

• 선택의 순간마다 당장 눈앞에 보이는 최적의 상황만을 쫓아 최종적인 해답에 도달하는 방법
• 탐욕 알고리즘의 문제를 해결하는 과정에서 매 순간, 최적이라 생각되는 해답(locally optimal solution)을 찾으며, 이를 토대로 최종 문제의 해답(globally optimal solution)에 도달하는 문제 해결 방식이다. 그러나 이 해결방식은 항상 최적의 결과를 보장하지는 못한다. 특정한 상황에서만 답이기 때문이다.
• 탐욕 알고리즘은 항상 최적의 결과를 도출하는 것은 아니지만, 어느정도 최적에 근사한 값을 빠르게 도출할 수 있는 장점이 있다.
• 탐욕 알고리즘을 적용하려면 해결하려는 문제가 다음의 2가지 조건을 성립하여야한다.
  1. 탐욕적 선택 속성(Greedy Choice Property): 앞의 선택이 이후의 선택에 영향을 주지 않는다.
  2. 최적 부분 구조(Optimal Substructure): 문제에 대한 최종 해결 방법은 부분 문제에 대한 최적 문제 해결 방법으로 구성된다.

3. Dynamic Programming(DP; 동적 계획법)

• 탐욕 알고리즘과 같이 작은 문제에서 출발한다. 그러나 탐욕 알고리즘이 매 순간 최적의 선택을 찾는 방식이라면, DP는 모든 경우의 수를 조합해 최적의 해법을 찾는 방식이다.
• DP의 원리는, 주어진 문제를 여러개의 하위 문제로 나누어 풀고, 하위 문제들의 해결 방법을 결합하여 최종 문제를 해결하는 문제 해결 방식이다. 하위 문제를 계산한 뒤 그 해결책을 저장하고, 나중에 동일한 하위 문제를 만날 경우 저장된 해결책을 적용해 계산 횟수를 줄인다. 즉, 하나의 문제는 단 한번만 풀도록 하는 알고리즘이 바로 DP 이다.
• 다음 2가지 가정이 만족하는 조건에서 사용할 수 있다.
  1. 큰 문제를 작은 문제로 나눌 수 있고, 이 작은 문제가 중복해서 발견된다.(Overlapping Sub-problems) 즉, 큰 문제로부터 나누어진 작은 문제는 큰 문제를 해결할 때 여러번 반복해서 사용 될 수 있어야한다.
  2. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 같다. 즉, 작은 문제에서 구한 정답을 큰 문제에서도 사용 할 수 있다. (Optimal Substructure) 즉, 주어진 문제에 대한 최적의 해법을 구할 때, 주어진 문제의 작은 문제들의 최적의 해법을 찾아야한다. 그리고 작은 문제들의 최적의 해법을 결합하면, 결국 전체 문제의 최적의 해법을 구할 수 있다.
• DP는 하위 문제의 해결책을 저장한 뒤, 동일한 하위 문제가 나왔을 경우 저장해 놓은 해결책을 이용한다. 이때 결과를 저장하는 방법은 memorization이라고 한다.
• memoriation의 정의는 컴퓨터 프로그램이 동일한 계산을 반복해야할 때, 이전의 계산한 값을 메모리에 저장함으로 써 동일한 계산의 반복 수행을 제거하여 프로그램 실행 속도를 빠르게 하는 기술이다.

4. 완전탐색

• 완전탐색이란 가능한 모든 경우의 수를 전부 확인하여 문제를 푸는 방식을 뜻한다.
• 모든 문제는 완전 탐색으로 풀 수 있다. 이 방법은 굉장히 단순하고 무식하지만, “답이 무조건 있다”는 강력함이 있다.
• 완전 탐색은 단순히 모든 경우의 수를 탐색하는 모든 경우를 통칭한다. 완전히 탐색하는 방법에는 brute force(조건/반복을 사용하여 해결), 재귀, 순열, DFS/BFS 등 여러가지가 있다.

5. 시뮬레이션

• 시뮬레이션은 문제에서 요구하는 복잡한 구현 요구 사항을 하나도 빠트리지 않고 코드로 옮겨, 마치 시뮬레이션을 하는것 과 동일한 모습을 그린다.
• 시뮬레이션은 모든 과정과 조건이 제시되어, 그 과정을 거친 결과가 무엇인지 확인하는 유형이다. 보통 문제에서 설명해 준 로직 그대로 코드로 작성되면 되어서 문제 해결을 떠올리는 것 자체는 쉬울 수 있으나 길고 자세하여 코드로 옮기는 작업이 까다로울 수 있다.

6.크롬 개발자 도구에서 함수 실행 시간 측정 방법

var t0=performance.now();
실행할 함수 쓰기
var t1 = performance.now();
console.log(“runtime: “ + (t1-t0) + ‘ms’)