알고리즘 선행개념 — 1. 시간복잡도

알고리즘과 시간복잡도

알고리즘을 위한 선행학습을 하기 이전에, 알고리즘이 무엇인지 먼저 짚고 넘어가려고 합니다. 알고리즘은 어떠한 문제를 해결하기 위한 절차나 방법을 공식화한 형태로 표현한 것을 말합니다. 즉, 문제 해결에 필요한 계산절차와 그에 맞는 프로그램 명령어들을 알고리즘이라고 합니다.
현재 위치에서 가고 싶은 곳으로 가는 길과 방법을 한 번 떠올려 볼 때, 여러 갈래와 교통편을 선택할 수 있습니다. 그중에서도 우리는 되도록이면 몸이 편하거나, 시간을 단축하거나, 돈을 아끼는 등 우리의 자원을 최대한 덜 쓰는 방향으로 선택을 하려고 하지요. 큰 에너지를 소모하고 싶지 않기 때문입니다. 그럼 컴퓨터도 우리랑 똑같이 덜 힘들기를 원할 수 있겠죠? 컴퓨터가 연산을 실행할 때 최대한 에너지(시간, 메모리 등)를 소모하지 않도록 최고의 방법을 선택하게끔 도와주는 척도가 바로 시간복잡도입니다.

시간복잡도는 연산의 갯수를 세어 얼마만큼의 연산이 수행되는지를 파악하고, 이를 통해 로직의 효율을 분석하는데 사용합니다.

시간복잡도 종류

시간복잡도의 종류는 크게 세 가지가 있어요.

1. Ο (Big-O) : 점근적 상한. ‘최악의 경우 n² 정도의 시간복잡도를 갖는다.’
2. Ω (Omega) : 점근적 하한. ‘잘 되면 1 정도의 시간복잡도를 갖는다.’
3. θ (Theta) : 상한과 하한의 교집합. ‘평균적으로 log n 정도의 시간복잡도를 갖는다.’

여기서 제일 안정적인 것은 아무래도 θ 세타 표기법이겠지만 계산하기가 번거로워서 잘 사용하지 않습니다. 범용적으로 사용하는 시간복잡도는 Ο 빅오 표기법이에요. 불필요한 연산을 줄이고 쉽게 계산할 수 있으며, 아무리 값이 안 좋게 주어지더라도 결과만큼의 시간복잡도는 보장해주기 때문입니다.

시간복잡도 계산

시간복잡도 계산 시 포함될 요소들과 규칙이 있으니 살펴보도록 하겠습니다.

계산할 때 포함되는 요소들

• 반복문 : for, while, foreach
• 조건문 : if
• 재귀호출

규칙

1. 시간복잡도는 n의 최고 차수만 나타낸다.
2. 시간복잡도에서 상수값은 무시된다.

입력값의 크기에 따른 함수의 증가량, 우리는 이것을 성장률이라고 부를 수 있어요. 이때 중요하지 않는 상수와 계수들을 제거하면 알고리즘의 실행시간에서 중요한 성장률에 집중할 수있는데 이것을 점근적 표기법(Asymptotic notation) 이라 부릅니다. 여기서, 점근적이라는 의미는 가장 큰 영향을 주는 항만 계산한다는 의미입니다. 즉, 우리가 n의 최고 차수만을 남기는 이유는 성장률에 집중하기 위해서예요.

👉 코드의 시간복잡도를 계산할 때 우리가 중점적으로 볼 것은 위의 ‘계산할 때 포함되는 요소들’이고, 계산한 결과에 대한 후처리는 ‘규칙’을 보고 적용하면 되어요.

대표적인 시간복잡도 예시

이제 간단한 예시를 가지고 대표적인 시간복잡도에 대해 이해해 봅시다.

Ο(1) : 상수

const arr = [1,2,3,4,5];
console.log(arr[1]);

위와 같이 입력 데이터 양에 상관없이 일정 시간 동안 실행될 때 ‘상수시간의 시간복잡도를 가진다’라고 합니다. 문제 해결을 위해 오직 한 단계만 거칩니다.

Ο(log n) : 로그

const arr = [1,2,3,4,5];
for(var i = arr.length-1; i >= 0; i/=2){
   console.log(arr[i]);
}

각 단계에서 모든 입력데이터를 볼 필요가 없을 때 ‘로그시간의 시간복잡도를 가진다’라고 합니다. 컴퓨터공학에서 로그의 밑은 2입니다. 각 반복문에서 i가 i/2, i/4가 되며 연산에 필요한 단계가 줄어들고 있습니다.

Ο(n) : 선형

const arr = [1,2,3,4,5];
for(var i in arr){
   console.log(arr[i]);
}

알고리즘의 실행시간이 입력데이터의 갯수에 따라 선형적으로(1대1로) 증가할 때를 나타냅니다.

O(n logn) : 선형로그

선형 로그 시간복잡도를 갖는 대표적인 정렬로 병합 정렬과 퀵 정렬이 있습니다. 병합정렬은 데이터를 반으로 잘게 쪼갠 후에 쪼개진 데이터를 정렬해서 다시 붙이는 방법입니다. 알고리즘 선행개념 정렬편에서 관련된 코드를 다루도록 하겠습니다:)

Ο(n²) : 제곱 square

const arr = [1,2,3,4,5];
for(var i in arr){
   for(var j in arr){
       console.log(arr[i]*arr[j]);
   }
}

일반적으로 for문이 이중으로 중첩되어 있는 케이스입니다. 배열의 길이만큼 반복하는 for문의 갯수가 늘어남에 따라 지수의 숫자가 증가합니다. (3개 중첩 -> n³) 대표적으로 버블 정렬과 삽입 정렬이 이 시간복잡도를 가집니다.

시간복잡도 구하는 팁

• 입력 데이터와 상관없이 단일 연산으로 끝나는 경우: O(1)
• 하나의 루프를 사용하여 단일 집합을 반복하는 경우: O(n)
• 단일 집합의 절반 이상을 반복하는 경우: O(n/2) -> O(n)
• 두 개의 다른 루프를 사용하여 두 개의 개별 집합을 반복할 경우: O(n+m) -> O(n)
• 중첩 루프를 사용하여 단일 집합을 반복할 경우: O(n²)
• 단일 집합을 쪼갠 후 정렬하여 다시 붙이는 과정이 있을 경우: O(n logn)

마치며

알고리즘 문제를 풀 때 일단 돌아가는 코드를 짜고 제출하자! 라는 생각으로 문제를 풀어왔던 것 같습니다. 일단 돌아가는 코드를 먼저 작성하고 이후에 수정하는 것도 문제 풀이에 대한 부담감을 줄여줄 수 있기 때문에 좋은 방법이에요. 하지만 시간제한이 있거나 효율성을 검사하는 문제에 있어서 코드가 통과하지 못할 때, 시간복잡도에 대한 개념이 없으니까 코드를 어떻게 수정해야 할지 감이 쉽게는 잡히지 않죠.. 때문에 시간복잡도를 익혀야겠구나 생각했습니다. 이왕 코드를 짤 때 컴퓨터가 덜 무리하는 쪽으로 배려해서 서로 윈윈하는 코드를 짜려고 노력해야겠습니다.