시간복잡도/공간복잡도

알고리즘 성능을 평가하기 위해 '복잡도(Complexity)'의 척도를 사용한다

• 시간 복잡도: 특정한 크기의 입력에 대하여 알고리즘의 수행 시간 분석
• 공간 복잡도: 특정한 크기의 입력에 대하여 알고리즘의 메모리 사용량 분석
  

표기법

1. 최상의 경우 : 오메가 표기법(Ω)
2. 평균의 경우 : 세타 표기법(Θ)
3. 최악의 경우 : 빅-오 표기법(O)

 시간 복잡도

 

 

최악의 경우를 계산하는 방식을 빅-오(Big-O) 표기법

 

 

 

O(1) (Constant)

입력 데이터의 크기에 상관없이 언제나 일정한 시간이 걸리는 알고리즘을 나타낸다 데이터가 얼마나 증가하든 성능에 영향을 거의 미치지  않는다

function exampleConstant(arr) {
    console.log(arr[0]);
}

O(log₂ n) (Logarithmic)

입력 데이터의 크기가 커질수록 처리 시간이 로그(log: 지수 함수의 역함수) 만큼 짧아진다

=>데이터가 10배가 되면, 처리 시간은 2배가 된다 이진 탐색이 대표적, 재귀가 순기능으로 이루어지는 경우도 해당된다

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

O(n) (Linear)

입력 데이터의 크기에 비례해 처리 시간이 증가한다.

=>데이터가 10배가 되면, 처리 시간도 10배가 됩니다. 1차원 for문이 있다

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

O(n log₂ n) (Linear-Logarithmic)

데이터가 많아질수록 처리시간이 로그(log) 배만큼 더 늘어난다

=>데이터가 10배가 되면, 처리 시간은 약 20배가 된다 정렬 알고리즘 중 병합 정렬, 퀵 정렬

 

O(n²) (quadratic)

데이터가 많아질수록 처리시간이 급수적으로 늘어난다

=>데이터가 10배가 되면, 처리 시간은 최대 100배가 됩니다. 이중 루프(n² matrix)가 대표적 단, m이 n보다 작을 때는 반드시 O(nm)로 표시하는 것이 바람직하다

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

function exampleCubic(n) {
    for (let i = 0; i < n; i++) {
        console.log(i);
        for (let j = i; j < n; j++) {
            console.log(j);
            for (let k = j; k < n; k++) {
                console.log(k);
            }
        }
    }
}

O(2ⁿ) (Exponential)

데이터량이 많아질수록 처리시간이 기하급수적으로 늘어난다

=>피보나치 수열이 있으며, 재귀가 역기능을 할 경우도 해당된다

 

시간제한에 따른 알고리즘 설계

공간 복잡도

작성한 프로그램이 얼마나 많은 공간(메모리)을 차지하느냐를 분석하는 방법

• 시간과 공간은 반비례적 경향이 있다
• 최근 대용량 시스템이 보편화되면서, 공간 복잡도보다는 시간 복잡도가 우선이다
• 알고리즘은 시간 복잡도가 중심이다

 

고정 공간:입력과 출력의 횟수나 크기와 관계없는 공간을요구저장공간

=>단순 변수, 고정 크기의 구조 변수, 상수

function sun(arr) {
  let total = 0
  for (let i = 0; i < arr.length; i++) {
    total += arr[i]
  }
  return total
}

 

가변공간:동적인 공간

function double(arr) {
  let newArr = []
  for (let i = 0; i < arr.length; i++) {
    newArr.push(2 * arr[i])
  }
  return newArr
}