amortized 검색 결과

해당 글 2건
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
c++ set이나 map을 전체 순회하는 데 시간 복잡도는 얼마일까요?

질문이 하나 들어왔습니다. 아래에 있는 foo 함수의 시간 복잡도는 어떻게 되나요? 쉽지 않은 질문입니다. c++에서 map이나 set은 self balanced binary Tree로 되어 있습니다. 흔히 '균형 트리' 라고 이야기를 합니다. 중요한 것은 어느 기준 점을 기준으로 왼쪽은 작은 것이, 오른쪽은 큰 것이 저장이 되어 있다는 것입니다. set이나 map이 Binary Tree의 속성을 가진다는 것은 시간 복잡도를 계산하는 데 굉장히 중요한 정보입니다. 즉, root를 기준으로 작은 것은 L, 큰 것은 R 부분에 있습니다. 그렇다면, iterator를, s.begin()부터, s.end()에 도달할 때 까지, 순회한다고 생각해 봅시다. 즉, 작은 것부터 큰 순서대로 순회를 한다고 하면 어떻게 ..
자료알고/자료구조 2020. 1. 31. 01:11