Analysis of Algorithms | Analysis of Loops

읽기 전

• 해당 게시물은 작성자가 학습한 내용을 정리 및 요약 목적으로 작성되었으므로 오역 및 오개념이 있을 수 있습니다. 바로잡기 위한 의견을 제시해주시면 매우 감사하겠습니다.

Analysis of Loops

알고리즘 문제를 해결함에 있어 시간복잡도는 매우 중요한 개념이고 코드에 포함된 연산과정이 어느 정도의 복잡도를 가지고 있는지 능숙하게 판단할 수 있는 지 여부가 전체 코드의 복잡도를 결정한다고 생각할 수 있다. 이번 게시글에서는 시간복잡도 함수 유형에 따라 어떤 연산의 형태를 갖는지 작성할 예정이다.

$O(1)$

loop를 포함하지 않고 1회성 연산임을 의미한다. swap()함수에 이에 해당한다. 그리고 정해진 횟수만큼 loop를 도는 경우에도 시간복잡도는 O(1)로 간주한다. [$c$]

// 여기서 c는 상수
for(int i=1; i<=c; i++){
  // 임의의 O(1) 연산 과정
}

위의 경우 loop문 내에 O(1)의 연산과정이 있고 주어진 input값에 관련이 없는 상수 c회 만큼 반복하는 코드의 예시이다. 위 코드의 전체 수행과정은 n과 연관이 없고 상수 c와 연관이 있기 때문에 O(n)이 아닌 O(1)이다.

$O(n)$

O(n)은 loop의 매개변수가 정해진 수만큼 순차적으로 증가하거나 감소하면서 시행되는 경우를 의미한다. [$\frac{n}{c}$]

// 여기서 c는 상수
for(int i=1; i<=n; i+=c){
  // 임의의 O(1) 연산과정
}

for(int i=n; i>0; i-=c){
  // 임의의 O(1) 연산과정
}

위의 경우 loop문 내에 O(1)의 연산과정이 포함되어 있고 주어진 input값에 따라 n만큼 반복하는 코드이며 매개변수는 최대 n부터 1까지 일정하게 c만큼 감소하거나 증가한다. c가 1이면 전체 수행과정은 n이고 c가 임의의 상수이면 $\frac{n}{c}$가 된다. 결국 코드의 수행시간은 n과 관련되어 있으므로 O(n)으로 표기할 수 있다.

$O(n^c)$

$O(n^c)$은 같은 횟수만큼의 loop가 nest형태로 이루어진 경우를 의미한다. [$\frac{n}{c}\cdot\frac{n}{c}$]

for(int i=1; i<=n; i+=c){
  for(int j=1; j<=n; j+=c){
    // 임의의 O(1) 연산과정
  }
}

for(int i=n; i>0; i-=c){
  for(int j=n; j>0; j-=c){
    // 임의의 O(1) 연산과정
  }
}

예제는 수행시간이 n인 loop문을 2번 감싸서 시간복잡도가 $O(n^2)$이다. 만약 k번 감싸면 시간복잡도는 $O(n^k)$가 될 것이다. 알고리즘 문제를 해결함에 있어 최적화된 해결방법을 찾을 수 없어 전수조사를 해야할 때 일반적으로 $O(n^2)$의 방법을 생각하게 된다. 만약 코드를 작성하였는데 $O(n^2)$이다 싶으면 더 최적화 할 순 없는지 다시 돌아가서 고민해보자. 물론 전체를 확실히 검사해야 하는 backtracking 기법도 문제에 자주 출제되고 있기 때문에 마냥 안좋게만 생각할 수는 없으니 문제 해결을많이 해보면서 감각을 키워야겠다..

$O(log\ n)$

$O(log\ n)$은 loop의 매개변수가 일정 값만큼 곰하거나 나뉘어질 경우를 의미한다. [$log_{c}n$]

for(int i=1; i<=n; i*=c){
  // 임의의 O(1) 연산과정
}

for(int i=n; i>0; i/=c){
  // 임의의 O(1) 연산과정
}

왜 매개변수가 일정 값만큼 곱하거나 나뉘어질 경우 시간복잡도가 $O(log\ n)$인지는 간단하다. 첫번째 loop의 매개변수는 1이고 점차 $c,\ c^2,\ \cdots,\ c^k$로 증가하는데 종료시점은 k가 $log_{c} n$값을 가짐으로써 매개변수가 n이 되는 시점이기 때문이다.

그러나 반복문 내 매개변수가 위와 같이 변하는 코드는 쉽게 볼 수 없다. 왜냐하면 보통 예제와 같이 코드가 작성되지 않고 재귀함수의 형태로 input값을 c만큼 나누거나 곱하기 떄문이다. 예를 들면, 이진탐색의 경우 처음 input은 크기가 n인 정렬된 배열이지만 1회의 연산 후 다시 함수를 호출할 때의 input은 2로 나눈 값으로 마지막 수가 남을 때까지 O(1)의 연산 후 호출된 함수에 입력하는 input값은 2로 나눈 값이다. 그러므로 이진탐색의 처음 input값은 n이고 매개변수를 나누는 상수값은 2로 [$log_{2} n$]의 형태로 표현된다는 것을 알 수 있다.

$O(log(log\ n))$

$O(log(log\ n))$은 loop의 매개변수가 지수함수적으로 증가하거나 나뉘는 경우를 의미한다. [$log_{c}(log_{i}n)$]

for(int i=2; i<=n; i=pow(i,c)){ // pow함수는 i^c의 값을 구한다.
  // 임의의 O(1) 연산과정
}

처음 매개변수가 $i$라고 할 때, 위의 코드처럼 매개변수의 지수가 c만큼 증가한다고 하자. 그러면 반복문의 매개변수는 $i^c,\ i^{c^2},\ \cdots,\ i^{c^k}$로 증가하는데 종료시점은 $i^{c^k}=n$이 되는 시점이다. 이 식을 만족하게 하는 k값은 $log_{c} log_{i} n$이므로 위의 코드의 시간복잡도는 $O(log(log\ n))$이 된다.

Calculating Time Complexity of loops

연속된 loop문에 대한 시간복잡도 계산

서로 종속되지 않고 분리된 반복문에 대한 시간복잡도는 각각 개별 loop문의 시간복잡도를 더한 뒤 input 값에 대해 정리한다.

for(int i=1; i<=m; i+=c){
  // 임의의 O(1) 연산
}
for(int j=1; j<=m; j+=c){
  // 임의의 O(1) 연산
}

위 코드의 경우 서로 종속되지 않고 input 값이 각각 m, n인 반복문이다. 첫 번째 반복문의 시간복잡도는 O(m)이고 두 번째 반복문의 시간복잡도는 O(n)이다. m, n이 각각 정해진 상수가 아니라면 전체 시간복잡도는 O(m+n)이고 만약 $m=n$인 경우 시간복잡도는 O(2n)이 된다.

loop문 내에 if문이 많이 삽입되어 있는 경우의 시간복잡도

알고리즘 문제를 해결함에 있어 최대한 불필요한 경우의 수를 줄이기 위해 if문을 많이 사용한다. 그러나 시간복잡도를 따질 때에는 최악의 경우를 가정하여 계산하는 것이 전체 수행시간을 판단할 때 안전하다. 그러므로 if문이 포함된 반복문의 시간복잡도는 모든 조건에 대해 만족하지 않아 모든 if문에 대해 검사를 진행했을 경우를 가정하고 계산해야 한다.

만약 if문이 너무 복잡하게 삽입되어 있는 경우라면 해당 if문이 최대 시간복잡도를 구한 뒤 치환하여 간략화할 수 있다.

재귀함수의 시간복잡도 계산

재귀함수는 $O(log\ n)$ 항목에서 설명하였듯이 반복되는 연산을 input값만 변화를 주게끔 하고자 사용된다. 그렇기 때문에 반복문의 성격으로 코드를 볼 것이 아니라 재귀함수를 호출하고 다음 재귀함수를 호출할 때 입력되는 input값이 어떻게 변화하는 지 확인하여 시간복잡도를 계산해야 한다. 이에 대해 재귀함수가 어떻게 전개되는 지 다음 포스팅에서 작성하고자 한다.

참고자료

1. Analysis of Loops