[질문] 시간 복잡도 이해가 잘 안가는데 헬프점

[익명(111.118)]

set 은 삽입하는데 O(log N ) 의 시간이 걸린다 라고 하는데

100만개의 원소를 삽입한다고 하면

1. 100만개의 원소를 다 삽입하는데 총 log(100만)  시간이 걸린다.

2. 첫 원소는 log1 시간, 두번째 원소는 log2 시간... 백만번째 원소는 log (100만)  시간 => 총합 = log1 + log2 + ... log 100만

둘 중에 뭐가 맞는 거에요

[익명(119.71)]

2

[익명(119.71)]

저게 100만 로그 100만이 되는 이유는 log n! = O(n log n)이기 때문임. 스털링의 공식 참고

[익명(119.71)]

상식적으로 100만개 입력만 받아도 100만인데 넣는데 로그 100만 걸리면 set은 신이노?

[페렛(quirrel)]

ㅋㅋㅋ이거왤케웃기지

[익명(111.118)]

감사함니다 선생님