Time Complexity

• Time Complexity(시간 복잡도)는 문제를 해결하는 데 걸리는 시간과 입력의 함수 관계를 가리킨다. ( ➡️ 입력값의 증가/감소에 따라 시간이 얼마나 증가/감소하는가?)
• 효율적인 알고리즘이란, 입력값이 커짐에 따라 증가하는 시간의 비율을 최소화한 알고리즘이다.
• 알고리즘의 시간복잡도는 주로 빅-오 표기법을 사용하여 나타내며, 이 빅-오 표기법은 계수와 낮은 차수의 항을 제외시키는 방법이다. 이런 방식으로 표현할 때, (예를 들면, 입력 크기를 무한대로 입력하여) 시간복잡도를 점근적으로 묘사한다고 말한다.

Big-O 표기법

• 알고리즘의 효율성을 평가하기 위한 분석법
• 시간 복잡도(실행 시간)와 공간 복잡도(실행 공간)로 이루어진다.
  

O(1) - constant complexity

처리해야 할 데이터 크기(입력값)에 상관없이 언제나 일정한 시간(언제나 일정한 결과)

O(n) - Linear complexity

처리해야 할 데이터 양에 비례해 실행 시간도 증가

function exampleLinear(n) {
    for (var i = 0 ; i < n; i++ ) {
        console.log(i)
    }
}

O(N^2) - Quadratic complexity

보통 반복문이 2번 중첩된 경우의 알고리즘. 처리해야 할 데이터양이 증가할수록 데이터양의 제곱만큼 실행시간이 증가한다.

for (int i = 0; i <n; i += c) {
    for (int j = 0; j < n; j += c) {
    // some O(1) expressions
    }
}

O(log n) -Logarithmic complexity

• 처리해야 할 데이터 양이 증가할수록 실행 시간이 약간씩 증가
• 실행 시간의 증가폭이 로그함수의 그래프를 갖기 때문에 급격히 증가하지는 않는다.
• 일반적으로 효율 높은 검색 알고리즘의 성능이 이에 해당한다.

function log(n) {
    for (let i = 1; i < n; i*=2) {
        const result = i;
        console.log(result);  
    }
}

Greedy Algorithm

• 탐욕 알고리즘은 최적해를 구하는 데에 사용되는 근사적인 방법으로, 여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달한다.
• 순간마다 하는 선택은 그 순간에 대해 지역적으로는 최적이지만, 그 선택들을 계속 수집하여 최종적(전역적)인 해답을 만들었다고 해서, 그것이 최적이라는 보장은 없다. 하지만 탐욕알고리즘을 적용할 수 있는 문제들은 지역적으로 최적이면서 전역적으로 최적인 문제들이다.

Dynamic Programming (동적 계획법)

• 동적 계획법 (dynamic programming)이란 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법
• 이것은 부분 문제 반복과 최적 부분 구조를 가지고 있는 알고리즘을 일반적인 방법에 비해 더욱 적은 시간 내에 풀 때 사용한다.