시간복잡도 줄이기(약수의 개수)

 

알고리즘 문제가 난이도가 올라가다 보면 시간 복잡도까지 고려해야 하는 경우가 있다.

약수의 개수에 대해 예시를 들자면, 만약에 12의 약수를 구하는데 있어서 아래의 코드를 먼저 생각할 수 있다.

fun before(n: Int): Int {
    var sum = 0
    for (i in 1..n) {
        if (n % i == 0) sum++
    }
    return sum
}

 

해당 코드는 만약 n 이 12일 경우, 1부터 12까지의 모든 수를 12로 나누었을 때 나머지가 0이 되는 것을 약수로 분류하는 경우이다. 이렇게 하면 약수의 개수를 구할 수 있지만, 1부터 12까지의 수를 전부 탐색해야 한다. 이때, 시간 복잡도를 O(n)이라고 이해할 수 있다.

 

하지만, 약수의 개수를 좀 더 쉽게 구할 수 있다.

 

case1) 약수의 개수가 짝수인 경우

n = 12 이라고 할 때, 약수는 1, 2, 3, 4, 6, 12 라고 할 수 있다. 이때, 1이 약수면 자동으로 12도 약수가 된다. (12%1==0 ↔ 12%12 ==0) 마찬가지로 2가 약수면 몫인 6도 약수, 3이 약수면 몫인 4도 약수이다.

따라서, 12까지 전부 세지 않고 1부터 3까지만 세면 각각에 대해 약수의 개수를 2를 더하여 약수를 구할 수 있다. 

 

case2) 약수의 개수가 홀수인 경우

n = 16 이라고 할 때, 약수는 1, 2, 4, 8, 16 이다. 이때, 1이 약수이면 몫인 16도 약수, 2가 약수이니 몫인 8도 약수가 된다.

이때 가운데에 짝을 이루지 못한 수 하나가 남는데, 이 수는 n의 제곱근이다. 즉, 만약 수가 n의 제곱근인 경우에는 약수의 개수를 1개만 세면 된다. 

따라서, 이 경우에도 16 까지 전부 세지 않고 1부터 16의 제곱근인 4까지만 세면 약수의 개수를 알 수 있다.

 

case1 의 경우에도 아까 1부터 3까지 세면 된다 했는데, 3의 기준이 무엇일까? 즉 12의 제곱근의 몫이다. 루트 12 는 루트 9와 루트 16 의 사이여서 3.xx 가 되는데 소수점을 버리면 된다. 

 

위의 설명을 아래에 코드로 옮겨보았다.

 

fun after(n: Int): Int {
    var sum = 0
    for (i in 1..sqrt(n.toDouble()).toInt()) { // sqrt : 제곱근
        if (i.toDouble().pow(2.0).toInt() == n) sum += 1 // 약수의 개수가 홀수인 경우
        else if (n % i == 0) sum += 2
    }
    return sum
}

 

sqrt는 제곱근, pow는 제곱수를 의미한다.

 

결론적으로, before 메소드의 시간 복잡도는 O(n)이 되는데 after 함수의 시간 복잡도는 O(√n) 으로 감소한다 (n이 크면 클수록 루트 성질에 의해 그 효과는 더 대단하다.)