[Array] contains(_:) + 시간복잡도 탐구

[Array] contains(_:) + 시간복잡도 탐구

Apple Developer Documentation

시퀀스가 주어진 요소를 포함하고있는지를 나타내는 불리언 값을 반환합니다.

선언

func contains(_ element: Self.Element) -> Bool

Element 가 Equatable 을 준수할 때 사용할 수 있습니다.

리턴값

만약 시퀀스 내에서 주어진 요소가 발견되면 true, 그렇지 않으면 false.

파라미터

element : 시퀀스에서 찾고자 하는 요소.

설명

이 예시는 영화의 캐스트를 담고 있는 배열에 가장 좋아하는 배우가 있는지 보기 위해 확인합니다.

let cast = ["Vivien", "Marlon", "Kim", "Karl"]
print(cast.contains("Marlon"))
// Prints "true"
print(cast.contains("James"))
// Prints "false"

복잡도

O(n), n은 시퀀스의 길이.

---

(아래는 제가 작성한 내용입니다)

contains(_:) 의 시간복잡도 탐구

Array에서 시간복잡도는 O(n) 이라고 공식문서에서 말한다.

하지만 탐색하는 요소를 빨리 찾으면 빨리 불린 값이 반환되지 않을까?

탐색하는 요소가 배열의 앞/중앙/뒤에 있을 때 각각 걸리는 시간을 알아보았다.

let startTime = CFAbsoluteTimeGetCurrent()
var arr = Array(repeating: 0, count: 1_000_000)
var arrFirst1 = arr
arrFirst1.insert(1, at: 0)
var arrMiddle1 = arr
arrMiddle1.insert(1, at: arrMiddle1.count / 2)
var arrLast1 = arr
arrLast1.append(1)
print(arrFirst1.contains(1))
//        print(arrMiddle1.contains(1))
//        print(arrLast1.contains(1))
let endTime = CFAbsoluteTimeGetCurrent()
print(endTime - startTime) // 0.00533902645111084

위와 같은 예제 코드를 만들어 실행시간을 측정해 보았다.

0으로 채워지고 길이가 1,000,000인 배열에 맨 앞(arrFirst1), 중간(arrMiddle1), 맨 뒤(arrLast1) 에 1을 넣는다.

그리고 각각의 배열에 contains(1) 을 적용하면 얼마나 걸리는지 측정한다.

(정확한 시간 측정을 위해 contains 줄은 하나만 남기고 나머지는 주석처리해 실행하는 식으로 진행)

print(arrFirst1.contains(1)) // 0.00533902645111084
print(arrMiddle1.contains(1)) // 0.03761601448059082
print(arrLast1.contains(1)) // 0.06794404983520508

확실히 찾는 요소가 맨 앞에 있을 때 가장 빨랐고, 찾는 요소가 맨 뒤에 있으면 가장 느렸다.

그리고 찾는 요소가 중간에 있으면 시간도 중간 정도로 걸렸다.

배열의 길이가 길어질수록 실행시간의 차이가 확실히 드러났다.

아래는 배열의 길이가 1,000,000,000일 때 (var arr = Array(repeating: 0, count: 1_000_000_000)의 실행시간이다.

print(arrFirst1.contains(1)) // 14.913639068603516
print(arrMiddle1.contains(1)) // 46.19543790817261
print(arrLast1.contains(1)) // 78.79820799827576

마지막으로 찾는 요소가 없을 때의 실행시간은 어떨까?

길이가 1,000,000이고 0으로만 채워진 원래의 배열 (arr) 에 contains(1) 을 적용해 얼마나 걸리는지 측정해 보았다.

let startTime = CFAbsoluteTimeGetCurrent()
var arr = Array(repeating: 0, count: 1_000_000)
var arrFirst1 = arr
arrFirst1.insert(1, at: 0)
var arrMiddle1 = arr
arrMiddle1.insert(1, at: arrMiddle1.count / 2)
var arrLast1 = arr
arrLast1.append(1)
print(arr.contains(1))
let endTime = CFAbsoluteTimeGetCurrent()
print(endTime - startTime) // 0.06914293766021729

결과는 위와 같았다. (물론 실행 시마다 오차는 조금씩 있다)

print(arrFirst1.contains(1)) // 0.00533902645111084
print(arrMiddle1.contains(1)) // 0.03761601448059082
print(arrLast1.contains(1)) // 0.06794404983520508
print(arr.contains(1)) // 0.06914293766021729

1이 없는 배열에서 1이 있는지 없는지 확인하려면, 결국 배열의 전체 요소를 끝까지 탐색해야 한다.

그래서 배열의 마지막에 1이 있는 경우(arrLast1) 보다 약간의 시간이 더 걸린 것을 확인할 수 있었다.

결론적으로 Array.contains(_:) 의 시간복잡도가 O(n)인 것은 맞지만 (시간복잡도는 최악의 경우를 가정하므로), 이 메서드는 배열의 첫 요소부터 하나씩 탐색하므로, 찾는 요소가 앞에 있다면 이보다 실행시간이 짧아질 수 있다는 사실을 알게 되었다!