[Kotlin] if - in 0..100 시간 복잡도

코틀린 문법 강의를 듣던 중, score가 Int 타입일 때

score in 0..100 은 모든 숫자를 비교해 시간 복잡도가 O(N) 이라

0 <= score && score <= 100 보다 비효율적이지 않을까 하는 생각이 들었다.

fun isInto0to100_1(score: Int): Boolean {
    return score in 0..100
}

fun isInto0to100_2(score: Int): Boolean {
    return 0 <= score && score <= 100
}

 

우려와는 다르게 바이트 코드를 확인해 보니 코틀린에서 아래와 같이 알아서 똑똑하게 최적화를 해주고 있었다.

쓸데없이 바이트코드가 길어지긴 하지만 가독성 측면에서 score in 0..100 으로 사용하는 게 좋을 것 같다.

public final class CompareKt {
    public static final boolean isInto0to100_1(int score) {
        boolean var10000;
        if (0 <= score) {
            if (100 >= score) {
                var10000 = true;
                return var10000;
            }
        }

        var10000 = false;
        return var10000;
    }

    public static final boolean isInto0to100_2(int score) {
        return 0 <= score && score <= 100;
    }
}

 

그렇다면 파이썬에서 if score in range(100) 의 시간 복잡도는 어떻게 될까?

Stackoverflow why is 100000000000000 in range 100000000000001 so fast in python-3

스택오버플로우에 자세히 나와있다.

간추려 보자면 2.x 버전에서는 O(N)이지만 3.x 버전에서는 아래와 같이 3가지를 검사해 O(1)이다.

1. step이 양수일 때 범위 내에 있는지
  positive steps: start <= ob < stop

2. step이 음수일 때 범위 내에 있는지
  negative steps: stop < ob <= start

3. (검사할 숫자 - 시작 숫자)를 step으로 나눈 나머지가 0인지
  result = ((int(ob) - start) % step) == 0

 

추가로 Decimal 을 사용한다면 모든 숫자를 비교해 O(N)의 시간 복잡도를 가진다고 하니 주의해야겠다.

sys.maxsize in range(sys.maxsize) # is pretty fast

# due to optimization - it's easy to compare given integer just with min and max of range.

Decimal(sys.maxsize) in range(sys.maxsize) # is pretty slow.

# in this case, there is no optimization in range,
# so if python receives unexpected Decimal, python will compare all numbers

 

파이썬으로 알고리즘을 풀 때 항상 이렇게 사용했었는데

if 0 <= score < n:

이제 이렇게 사용해 보는 것도 고려해 볼 수 있겠다.

if score in range(n):