알고리즘 빅 오 표기법 살펴보기

알고리즘 빅 오 표기법 살펴보기

개요

• 알고리즘을 문제 은행에서 푼 기억은 있어도 알고리즘에 대해 공부한 적이 없어서 이 참에 공부하면서 정리하기로 마음 먹었습니다.
• 어려운 내용은 제가 이해를 못하니 간단하게 한번 살펴 보겠습니다.
• 처음으로 살펴볼 내용은 빅 오 표기법입니다.

빅 오 표기법이란

• 시간 복잡도(알고리즘의 시간 효율성)를 쉽게 소통할 목적으로 자료 구조와 알고리즘의 효율성을 간결하고 일관된 언어로 설명하기 위해 수학적 개념을 차용했습니다.
• 이러한 개념을 형식화한 표현을 빅 오 표기법이라고 부릅니다.
• 지금 설명은 수학적 관점을 최대한 배제하고 있습니다.(아주 쉬운 버전)

빅 오: 단계 수 계산

O(1)

• "빅 오1", "차수 1"이라고 부르며, 오 1이라고 편히 부르겠습니다.
• O(1)은 데이터 크기에 상관없이 알고리즘에 필요한 단계 수가 일정하다는 의미입니다. 즉, 배열에 길이가 얼마인지 상관없이 한 단계면 됩니다. 예를 들면, 배열의 끝의 삽입과 삭제가 있습니다. 마지막 배열 요소만 삭제하거나 추가하는 한단계만 수행하면 됩니다.
• 항상 단계 수가 일정하므로 상수 시간(constant time)이라고 불립니다.

O(N)

• 한번에 하나씩 검색하는 선형 검색의 효율성은 O(N)으로 표기한다. 맨 처음 단계(첫 요소)에서 검색이 완료될 수 있지만 최악의 경우 마지막 단계(마지막 요소)까지 가야됩니다.
• 배열 내에 N개의 원소가 있을 때 알고리즘을 끝내는데 N개의 단계가 필요함을 표현하는 "빅 오"의 방법입니다.
• 데이터가 많아 질수록 알고리즘에 필요한 한 단계 수도 늘어나므로 선형 시간(linear time)이라고 불립니다.

O(log N)

• 계속 반으로 나눠서 검색하는 이진 검색을 O(log N)라고 부릅니다. O(1)과 O(N) 사이쯤이라고 생각하면 됩니다.

• "오 로그 N"이라고 읽습니다., 데이터가 2 배로 증가할 때마다 한 단계식 늘어나는 알고리즘을 설명합니다.

• 효율성은 아래 순서대로 좋습니다.

O(1) - 1
O(log N) - 2
O(N) - 3

• 위 이미지를 보면 Number of Operations(단계 수)와 amout of data(원소 수)로 그려진 그래프가 있습니다.
• O(1)은 일정하지만, 반면에 O(N)은 대각선으로 쭉 뻗어나가고 있습니다. 원소수에 비례해서 계속 뻗어나갑니다.

실제 예제

const lastNames = [
  'lee',
  'kim',
  'oh',
  'Nam'
]

for (const lastName of lastNames) {
  console.log(`Here's a lastName : ${lastName}`)
}

//
"Here's a lastName : lee"
"Here's a lastName : kim"
"Here's a lastName : oh"
"Here's a lastName : Nam"

• 이 알고리즘 효율성을 빅 오 표기법으로 나타내면 O(N)입니다.
• 리스트 요소 4개가 있는데 콘솔에 4개가 찍혔다., 즉, for문이 4단계가 걸린다.
• 만약 100개라면 100단계가 걸릴것이다.

console.log('Hello World');

• 이건 시간 복잡도가 O(1)입니다. 항상 1단계만 걸리기 때문입니다.

const isPrime = (number) => {
  for(let i = 2; i < number; i++) {
    return number % i === 0 ? false : true
  }
}

console.log(isPrime(17)); // true
console.log(isPrime(5)); // true
console.log(isPrime(3)); // true
console.log(isPrime(4)); // false
console.log(isPrime(8)); // false
console.log(isPrime(10)); // false

• 위 코드는 소수를 구하는 함수입니다.

• 1과 매개변수로 넘어간 자기자신 number를 제외한 그 사이의 수들로 나눠서 만약 나머지가 0인게 있으면 소수가 아니고 없을 경우 소수입니다.

• 이 알고리즘 효율성은 O(N)입니다. 실질적으로 1과 number를 제외하므로 N-2 이지만 N이 커질수록 알고리즘 단계도 커지므로 2라는 숫자는 N이 1,000,000일때는 큰 의미가 없으므로 무시합니다.

결론

• 알고리즘 풀면서 시간복잡도에 대한 이야기를 들었지만 문제를 풀때는 답을 맞추기에 급급해서 큰 신경을 쓰지 못했습니다.
• 알고리즘 시간 복잡도 빅오를 통해서 코드를 짤때, 문제를 풀때 최적의 코드를 짤 수 있을것 같습니다.
• 여기서 설명하지 못한 빅오 표기법들은 나중에 포스팅하겠습니다.

참조

• 웹 개발자를 위한 자료구조와 알고리즘 (#01. 빅오 표기법)