왜 set.has()는 O(1)인가?

시간복잡도애서 O(1)이란?

• 문제를 끝내는데 오직 한단계만.. 상수
• O(N)의 경우, 문제를 해결하기 위한 단계의 수와 입력값 n이 1:1 관계를 가지게 되며, 입력이 증가하면 처리 시간또는 메모리 사용이 선형적으로 증가한다.

sameValueZero 알고리즘

• 표
  
  

array.include() vs set.has()

• sameValueZero알고리즘 기반으로 한 set.has()는 O(1)
• array.include() 가져오고 비교하고 식의 단계를 거치기에
  O(N)

테스트 해보기

const test = () => {
const MAX = 10000000
let a = []
a.length = MAX

for (let i = 0; i < MAX; i++) {
  a[i] = i
}

let s = new Set(a)

let o = a.reduce((acc, e) => {
  acc[e] = e
  return acc
}, {})

console.time("Test_Array.IndexOf(0)\t")
a.indexOf(0);
console.timeEnd("Test_Array.IndexOf(0)\t")
console.time("Test_Array.IndexOf(n/2)\t")
a.indexOf(MAX / 2);
console.timeEnd("Test_Array.IndexOf(n/2)\t")
console.time("Test_Array.IndexOf(n)\t")
a.indexOf(MAX);
console.timeEnd("Test_Array.IndexOf(n)\t")

console.time("Test_Set.Has(0)\t\t")
s.has(0)
console.timeEnd("Test_Set.Has(0)\t\t")
console.time("Test_Set.Has(n/2)\t")
s.has(MAX / 2)
console.timeEnd("Test_Set.Has(n/2)\t")
console.time("Test_Set.Has(n)\t\t")
s.has(MAX)
console.timeEnd("Test_Set.Has(n)\t\t")

console.time("Test_Object[0]\t\t")
o[0]
console.timeEnd("Test_Object[0]\t\t")
console.time("Test_Object[n/2]\t")
o[MAX / 2]
console.timeEnd("Test_Object[n/2]\t")
console.time("Test_Object[n]\t\t")
o[MAX]
console.timeEnd("Test_Object[n]\t\t")
}