평균복잡도 검색 결과

해당 글 3건
amortized 복잡도 : average complexity와 뭐가 다른가요?

링크는 c++의 vector의 push_back에 대해서 설명한 문서입니다. Complexity가 constant라고 되어 있는데요. 괄호가 떡하니 쳐져 있습니다. amortized time이라고요. 이게 왜 나왔는지부터 예를 들어서 이야기 보겠습니다. vector의 초기 size가 무한대이지 않는 이상 (기본적으로 적절한 size) 최악의 경우에는, O(vector의 size) 만큼 나올 겁니다. 만약에 n개가 있으면 O(n)이 나올 겁니다. 더 정확하게 말하면 linear time 입니다. worst case인 경우에는 그게 맞습니다. 기존에 n개의 item이 있었습니다. capaity 역시 n이였고요. 만약에 grow rate가 2인 경우에, 이 시점에서 push_back이 호출된 경우에, 2배로 ..
자료알고/알고리즘 2020. 7. 16. 01:42
재해싱 (rehashing) : 시간 복잡도를 분석해 보면서 왜 필요한지 알아봅시다.

Hash에서, 면접에서 물어볼 만한 키워드들을 천천히 알아보도록 하겠습니다. 이 중 오늘은 재해싱에 대한 이야기를 간단하게 하고 넘어가겠습니다. Hash Table은, 저번시간에 배운 바로는, 버킷에다가, 데이터를 주렁 주렁 매달아 놓는 식으로 많이 처리를 한다고 했었습니다. 보통, Chaining을 사용하는 경우, List를 사용한다고 했었습니다. 저는 간단하게 구현하기 위해서, 2차원 배열로 구현을 했었고요. 그런데, 생각을 해 봅시다. 수가 2개만 들어왔어요. 그런데, 1000만개의 바구니를 미리 만들어 놓을 필요가 있을까요? 2개를 위해서, 1000만개의 바구니를 생성한다. 이것만큼 낭비가 없습니다. 그러면, 어떻게 할 거냐. 초기 사이즈를 매우 작게 잡습니다. 예를 들자면, 2개의 초기 buck..
자료알고/자료구조 2019. 9. 13. 00:59
퀵 정렬 평균 시간 복잡도 : 왜 O(nlogn)일까?

평균적으로 퀵 정렬은 머지보다, 빠른 것으로 알려져 있습니다. 물론 최악의 경우에, skew만 계속 일어나면, 별로 좋지는 않겠지만요. 이건 왜 그럴까요? 머지에 비해서 Quick은 추가적인 공간을 쓰지 않기 때문에 그렇습니다. 사실, 이게 제일 큰 요인입니다. 이것이 어떻게 동작하는지 이해가 가지 않으시다면, 관련 글을 보고 오시는 것도 좋겠습니다. [관련글] 퀵 정렬에 대해서 알아봅시다. 그러면 평균 복잡도는 왜 O(nlogn)일까요? 몇 가지 가정을 해 봅시다. partition이 일어날 때, arr[0]을 pivot으로 잡습니다. 이 때, 정렬을 할 데이터의 갯수가 n개라고 하면, arr[i]보다 작은 것의 갯수가 0개, 1개, 2개, ... , n-1개인 경우가 있을 거에요. 그러한 확률이 모두..
자료알고/알고리즘 2019. 8. 20. 16:18