알고리즘의 조건
입력, 출력, 유한성, 명확성, 효율성
알고리즘을 어떻게 해야 잘 풀수 있을까?
문제를 이해한다.
입출력예시, 제한사항, 주의사항을 토대로
문제를 어떻게 해결할 수 있을지 전략을 세운다.
수도코드를 작성하기 전에 인간의 사고로 문제를 해결해본다.
수도코드를 작성한다.
막힌다면 설명을 하면서 해결되기도 한다.
문제를 코드로 옮긴다.
최적화를 시도한다.
빅오
효율적인 알고리즘 : 입력값이 커짐에 따라 증가하는 시간의 비율을 최소화한 알고리즘
입력값의 변화에 따라 연산을 실행할 때 연산 횟수에 비해 시간이 얼마만큼 걸리는가?를 표기하는것이 빅오 표기법이다.
빅오는 최악의 경우를 고려한다.
시간복잡도
O(1) constant complexity
배열에서 인덱스로 출력할 대상을 찾는 것은 Orderd 1의 시간 복잡도를 갖고있다.
O(n) linear complexity
n이 증가함에 따라 시간도 비례해 증가한다.
반복문을 돌릴때 여기에 해당한다. for문을 1만큼 돌릴때와 10만큼 돌릴때의 연산 횟수는 10배차이가 난다.
빅오에서 상수는 의미가 없으므로 O(2n) 이나 O(n+10) 이런식으로 표기하지 않는다. 두 경우 모두 O(n)이다.O(log n) logarithmic complexity
이 경우는 O(1)다음으로 빠른 경우에 해당한다.
처음에는 O(n)과 같이 n의 증가에 비례해 우상향하지만 점점 n이 커질수록 완만한 곡선을 이룬다.O(n^2) quadratic complexity
입력값이 증가함에 따라 연산이 n의 제곱수의 비율로 증가한다.
이중for문과 같은 경우 이에 해당한다.O(2^n) exponential complexity
가장 느린 경우에 해당한다.
재귀로 구현하는 피보나치 수열이 이에 해당한다.
데이터 크기에 따라 만족해야 하는 복잡도
입력 크기가 클 때는 O(n), O(logn)의 시간복잡도에 해당할 수 있도록 문제를 풀어야 한다.
데이터 크기 제한 예상되는시간 복잡도 n ≤ 1,000,000 O(n) or O (logn) n ≤ 10,000 O(n2) n ≤ 500 O(n3)
공간복잡도
알고리즘이 수행되는 데 필요로 하는 메모리공간의 크기를 말한다.
시간복잡도에 더 집중해야 하지만 공간복잡도를 중요하게 보는 경우도 있다.
동적계획법같은 경우, 하드웨어 환경이 한정되어있는 경우.
Greedy 탐욕법
선택의 순간마다 당장 눈앞에 보이는 최적의 상황만을 쫓아 최종적인 해답에 도달.
1. 선택 절차(Selection Procedure)
현재 상태에서의 최적의 해답 pick
2. 적절성 검사(Feasibility Check)
선택된 해가 문제의 조건 만족하는지 check
3. 해답 검사(Solution Check)
원래의 문제가 해결되었는지 검사.
해결되지 않았다면 다시 동일과정 반복
최적의 결과를 도출하는 것은 아니지만 어느정도 최적에 가까운 값을 빠르게 도출할 수 있다.
함수 실행시간 측정하기
var t0 = performance.now();
fib(50); // 여기에서 함수 실행을 시켜주세요
var t1 = performance.now();
console.log("runtime: " + (t1 - t0) + 'ms')