다들 알고리즘과 자료구조를 공부하시다 보면 시간복잡도를 마주하실 겁니다.
O(n), O(1) 많이 들어는 봤지만 대체 이게 뭘까요? 무엇을 뜻하는걸까요?
관련해서 쉽고 짧게 정리 해 보려고 합니다.
자료구조 / 알고리즘
일단 시간복잡도를 얘기하기 위해선 자료구조와 알고리즘에 대해서 먼저 얘기를해야 합니다. 이미 정리가 잘 된 자료들이 많으니, 이 포스팅에서는 제 사견을 곁들여 최대한 쉽게 얘기 해 보겠습니다.
자료구조
자료구조란 데이터가 저장된 구조(형태)를 뜻합니다. 데이터는 사용 될 때 서버로 전송되기도 하고 사용자에게 회면을 보여주기도 합니다. 데이터는 일반 텍스트가 되기도 하고 숫자가 되기도 하며 반복이 되는 표 형태 등등 여러가지 형태가 될 수 있습니다. 그렇기 때문에 프로그램에서 데이터들을 잘 보여주기 위해서는 데이터가 어떻게 저장되어야 할지가 중요해지겠죠? 만약 몇만줄씩 반복되는 표가 있다면 이 중요성은 더욱 커질 겁니다.
코드로 예를 한번 들어볼까요? 아래는 숫자를 합하여 평균을 구하는 코드 입니다.
성적표 평균 구하기
const 수학 = 50
const 국어 = 70
const 영어 = 20
const 평균 = 수학 + 국어 + 영어 / 3위의 코드는 각 과목의 점수를 변수에 담아서 다 더한 후 과목 수 만큼 나눠주는 코드입니다. 자 위 코드에서의 문제점은 무엇일까요? 과목이 추가 된다면 변수에 과목을 추가해주고 평균을 구하는 코드에 추가된 과목을 더해주고 과목 수가 추가 되었으니 나눠주는 과목수도 수정을 해줘야 합니다. 불편하죠? 자 그럼 동일한 코드를 자료구조만 바꿔서 개선 해 보겠습니다.
성적표 평균 개선하기
const 점수목록 = [50, 70, 20]
const 평균 = 점수목록.reduce((총합, 점수, 순번, 점수목록) => {
총합 += 점수
return 총합 / 점수목록.length
}, 0)자 각 과목의 점수들을 배열에 담았습니다. 어떻게 되었나요? 위의 코드는 배열에서 사용가능한 reduce 함수를 사용했습니다. 점수목록 배열에 점수만 추가 해 준다면 평균을 자동으로 구해줍니다. 과목을 변수에 추가해 줄 필요도 없고, 과목을 더해서 과목수만큼 나눠주는 것도 자동으로 처리해줍니다.
이렇게 자료구조만 변경해주니 많은 것들이 개선되고 편해졌습니다. 현재는 데이터가 몇개 없어서 별 차이가 없어보이지만 프로덕트 레벨에서 다뤄야하는 수많은 데이터라면 훨씬 그 차이가 커질 겁니다. 바로 이게 자료구조이며 자료구조의 중요성 입니다.
알고리즘
그렇다면 알고리즘이란 무엇일까요? 더 간단하게 설명 가능합니다.
알고리즘은 주어진 문제를 해결하는 방법을 의미합니다.
위의 성적표 코드에서는 평균을 구하는 부분을 예를들수 있겠네요. 결국 자료구조와 알고리즘은 뗄 수 없는 관계이니 두가지 다 명확한 개념을 알고 같이 공부를 해야 합니다.
같은 자료구조의 문제를 해결하거나 형태가 다른 자료구조의 문제를 해결 할 때도 다 다른 여러가지의 알고리즘을 사용하게 됩니다. 알고리즘이 다 다르다면 우리는 좋은 알고리즘을 선택해서 사용해야 합니다.
좋은 알고리즘이란 무엇일까요? 저는 좋은 알고리즘이란 요구사항과 상황에 맞는 알고리즘을 선택하는게 좋은 알고리즘이라고 생각합니다.
예를들어 메모리가 높아도 속도와 성능이 필요한 알고리즘이 있을 수 있고, 메모리를 적게 사용하는 알고리즘이 필요 할 수 있습니다.
이렇게 알고리즘은 요구사항과 상황에 맞는 알고리즘을 선택해야 합니다. 하지만 보통 일반적으로는 알고리즘의 속도를 성능의 척도로 생각합니다.
이를 시간 복잡도라고 표현합니다.
시간복잡도란?
시간복잡도도 제 사견을 덧붙여 풀어서 설명해보도록 하겠습니다.
시간 복잡도란 알고리즘이 문제를 해결하는데 소요되는 시간을 의미 합니다. 허나 시간은 컴퓨터의 성능 등으로 사용자 환경에 따라 다르기 때문에 시간 소요에 따른 알고리즘을 평가하기엔 어려움이 있습니다.
그렇기 때문에 보통 알고리즘을 평가 할때에는 반복문 등 코드 성능에 부하가 생길만한곳을 찾아 알고리즘을 적용시켜 실행 시간을 예측하는 방법 등을 사용합니다.
예를 들어 아래와 같습니다
배열에서 특정 값을 찾으시오
const 배열 = [0, 1, 2, 3, 4, 5]
// 0을 찾을 경우(한번에 찾을 경우) = 최선의 경우
// 2 또는 3을 찾을 경우(중간에 찾을 경우) = 평균의 경우
// 5를 찾을 경우(마지막에 찾을 경우) = 최악의 경우이를 아래와 같이 표현이 가능합니다.
Big-Ω : (한번에 찾을 경우) 최선의 경우
Big-Θ : (중간에 찾을 경우) 평균의 경우
Big-O : (마지막에 찾을 경우) 최악의 경우
이중에 평균의 경우인 Big-Θ와 최악의 경우인 Big-O를 주로 사용하는데 제일 많이 사용하는건 일반적으로 Big-O표기법 입니다.
Big-O
Big-O 표기법은 O(n)으로 표기합니다. 위의 배열로 예를들면 배열의 길이가 6이기 때문에 해당 배열의 최악의 경우는 6번을 탐색해야 하므로 O(6) 입니다. 그렇기 때문에 표기는 O(n)으로 표기합니다.
n에 1을 대입하면 계산량은 한번, 100을 넣으면 100을 계산하기 때문에 그래프로는 일차함수 그래프의 모양을 띄고 있습니다. 이런 이유로 O(n)의 알고리즘은 선형시간 알고리즘이라고 표현합니다.
선형시간 알고리즘의 경우 코드의 수행시간이 입력의 크기에 정비례하므로 대게 우리가 찾을 수 있는 알고리즘 중 가장 좋은 알고리즘인 경우가 많다고 합니다.
추가적으로 입력에 상관없이 상수만큼의 시간이 소요되는 알고리즘을 상수시간 알고리즘이라고 합니다. 상수시간 알고리즘은 문제 해결을 위해 계산량이 100번이 되더라도 입력값이 상관없기 때문에 O(1)로 표현합니다.
이 외에도 O(logn), O(n!), O(2n), O(n²), O(nlogn) 등의 표기법이 있습니다.
이 중 성능은 O(n!) 제일 좋지 않습니다.
마지막으로 Big-O 표기법의 특징을 말해보겠습니다. Big-O 표기법은 최악의 경우를 표현하기 때문에 계산에 가장 많은 영향을 미치는 항만 표기합니다. 그리고 상수는 큰 의미가 없으므로 제거해줍니다. 예를 들면 아래와 같습니다.
Big-O 표기법
5n² + 1000n 의 표기는?? 아래와 같습니다.
5n² + 1000n ➔ O(5n²) ➔ O(n²)
마무리
이정도만 알아도 시간복잡도에 대해서 어느정도의 이해가 되셨을거라고 생각합니다.
자료구조 및 알고리즘 공부에 참고가 되었으면 합니다.
다른 표기법도 필요 시 한번씩 보시는걸 추천 드립니다.
감사합니다 :)
