[CS] 시간복잡도가 가진 허점과 캐시히트 (Cache hit) 의 중요성

오규성·2025년 11월 2일

이번에 백준 연습을 하는데 소수 구하기 + 슬라이딩 윈도우 를 활용해야하는 문제를 풀게 되었다.

소수를 구해야하므로 당연히 에라토스테네스의 체를 이용하려고 하였는데, 뭔가 더 좋은 방법이 없을까 싶어 찾아보니 에라토스테네스의 체[O(N log log N)] 보다 빠른 오일러의 체[O(N)] 가 존재한다길래, 허겁지겁 이것을 이용해 풀어보았다.

그런데 ...?

에라토스테네스의 체가 오일러의 체보다 훨씬 빠르게 처리된 것을 알 수 있었다.

아니, O(N) 이라면서 O(N log log N) 보다 늦게 처리되는게 말이 되나? 싶어서 이 글을 작성하게 되었다.

이론과 실전은 다르다.

이론적으로는 오일러의 체가 에라토스테네스의 체 보다 훨씬 빠르고, 나도 그렇게 알게 되어 오일러의 체 를 적극 사용하려고 하였으나 실제 사용결과 에라토스테네스의 체 가 메모리, 시간 비용 측면에서 더 효율적이었다.

N = 4천만으로 개인적으로 테스트 한 결과. 에라토스테네스의 체가 훨씬 빠르게 나왔다.

백준에서도 똑같이 에라토스테네스가 더 빠르게 나왔다.

어떻게 O(N) 인 오일러의 체가 O(N log log N) 인 에라토스테네스의 체보다 느린 결과가 나온 것일까?

캐시 히트의 중요성

그 이유는 바로 캐시 히트에 존재한다.

다시 한 번 코드를 살펴보자.
에라토스테네스의 체의 경우 계산이 매우 단순하고 반복적인 것을 알 수 있다.

fun main(){
    val isPrime = BooleanArray(n + 1){ true }

    isPrime[0] = false
    isPrime[1] = false

    for(i in 2 .. kotlin.math.sqrt(n.toDouble()).toInt()){
    	// i + i 부터 시작하여 i 의 배수만큼 step 을 뛴다.
        if(isPrime[i]){
            for(j in i + i .. n step i){
                isPrime[j] = false
            }
        }
    }
}

i + i 부터 시작하고, i의 배수만큼 step 을 띄는 한 가지 상황만 알면되며, isPrime 배열에만 접근하면 된다.

그러므로 메모리 접근 패턴이 매우 규칙적이고 순차적이기 때문에 CPU의 캐시 히트율이 증가한다.

이제 오일러의 체를 살펴보자.

fun main(){
    val primeList = mutableListOf<Int>()
    val numberArr = IntArray(n + 1){ it }

    for(i in 2 .. n){
        if(numberArr[i] == i) primeList.add(i)

        for(p in primeList){
            if(p > numberArr[i] || p * i > n) break
            numberArr[i * p] = p
        }
    }
}

한 눈에 보더라도 접근하는 객체가 많고, 처리할 것도 많다.

numberArr 배열에 접근하고

primeList 에 접근하고,

numberArr[i * 불규칙적인 소수] 에 접근한다.

또한 불규칙적인 소수값에 따라 break 도 진행된다.

위와 같이 불규칙적인 조건들과 여러 배열에 대한 접근 탓에 효율적인 캐싱이 발생할 수 없어 매번 불필요한 계산이 진행되게 된다.

배열에서의 캐시 히트

캐시히트와 관련된 다른 예로 배열이 존재한다.

2차원 배열 arr[i][j] 가 존재한다고 하자.
i와 j의 최대값이 500 이라면 arr[500][500] 이 최대값일 것이다.

하지만 실제로 컴퓨터에게는 2차원 배열이라는 것은 존재하지 않다.
그저 행을 우선 순위로하는, 길게 이어진 1차원 공간만이 존재할 뿐이다.

만약 우리가 i 와 j 의 원소를 더 해야하는 문제를 풀고 있다고 가정해보자.

i행을 우선으로 접근하고 j열 순회

fun sum_row_major(arr: Array<IntArray>): Long {
    var sum = 0L
    val rows = arr.size
    val cols = arr[0].size

    for (i in 0 until rows) {
        for (j in 0 until cols) {
            sum += arr[i][j]
        }
    }
    return sum
}

위의 코드는 i 를 먼저 순회하며 j를 순회하고, sum 에 원소값을 더하는 코드이다.
즉, i 행을 먼저 접근하고 i행에 해당하는 j 열에 접근한다.

대부분의 언어들은 행을 기준으로 메모리에 적재하기 때문에, 위처럼 i 행에 먼저 접근한다면 i행에 해당하는 메모리들을 캐싱한다.

예시 순서는 다음과 같다.

i = 0 행에 접근하였으나, 캐싱된 메모리가 없다. 0행에 해당하는 일부 데이터를 가져와 캐싱한다.

0행에 해당하는 j열을 순회한다. 캐싱 데이터가 존재하여 캐시 히트가 발생한다.

접근 시간이 빨라진다. 이후 캐싱 데이터가 존재하지 않다면 다시 데이터를 가져와 캐싱한다.

이 경우 캐시 기능을 통해 접근 속도가 매우 빨라지므로 효율이 매우 좋아진다.

j 열을 먼저 접근하고 i행 순회

fun sum_column_major(arr: Array<IntArray>): Long {
    var sum = 0L
    val rows = arr.size
    val cols = arr[0].size

    // 바깥쪽 루프가 열(j)을, 안쪽 루프가 행(i)을 순회
    for (j in 0 until cols) {
        for (i in 0 until rows) {
            sum += arr[i][j]
        }
    }
    return sum
}