String에 +연산을 하셨네요. 어떤 일이 일어날까요?

1번. s = s + a

s = (new StringBuilder(s)).append(a).toString();

헤헤^^;; 가비지가 마니 마니 생성되라고 하는 코드네요. 어떻게 바꾸셔야 할까요?

64번째 줄 String ans를, StringBuilder나 StringBuffer로 바꾸신 다음에 append 메서드를 호출하는 식으로 짜시면 됩니다.

! 알아두면 좋은 팁

실제로 StringBuilder나 StringBuffer는 내부적으로 동적 배열 (Dynamic array)로 구현이 되어 있어요.

아래 소스 코드를 실행시키시면 expand 연산이 일어날 때 마다 capacity가 어떻게 변하는지 확인 가능하실 거에요.

wand에서 돌리면

8 16
16 16
24 34
32 34
40 70
48 70
56 70
64 70
72 142

이런 식으로 나오는 것을 알 수 있는데, expand 연산이 일어날 때 마다, 2배씩 capacity가 뻥튀기 되는 것을 알 수 있어요.

(정확히는 2*old_capacity + 2 = new_capacity)

Q. 그러면 append 연산은 복잡도가 어떻게 될까요?

와우...우선 정말 감사합니다 ㅠㅠ

누추한 질문에 이런 귀한분이 오시다니..

가희님 덕분에 새로운 사실도 공부하고 많이 배워갑니다!

append연산은 배열의 크기를 늘리기 때문에

새로운 배열을 생성하고 값을 복사하는 과정에서 O(n)의 복잡도를 가지지 않을까..하고 생각했습니다.

그리고 답을 확인하기 위해 인터넷 검색을 하던 도중 우연히 가희님 블로그에서 글을 보고 정답이 O(1)이란 것을 알게되었습니다!

그런데 append  함수에서 arraycopy 함수도 결국 깊은 복사를 하는 것이기 때문에 결론적으론 복잡도가 O(n)이 아닌가..하는 의문이 듭니다..

검색을 통해 해결하려고 했지만 제가 많이 부족합니다 ㅠㅠ 한 번만 더 배움을 주세요..

arrayCopy는 배열의 내용을 그대로 복사하기 때문에, 사실 배열의 크기만큼 복잡도를 가지는 게 맞아요.

그런데 expand가 몇 번 호출되느냐가 문젠데..

초기 capacity가 1이였습니다. 확장될 때 기존 크기의 2배가 된다고 했을 때

size가 2^20+1이 되기 위해서는 capacity가

1, 2, 4, 8, 16, 32, 64, 128, 256, 2^9, 2^10, ... , 2^20, 2^21이 되어야 합니다.

그러면 할당한 메모리의 총 capacity는 1+2+...+2^21 = 2^22 - 1이고

말씀드린 arrayCopy는 1에서 2로 변할 때 1, 2에서 4로 변할 때 2, ... 2^20에서 2^21로 변할 때 2^20만큼 복사했기 때문에

복사 비용은 1+...+2^20 = 2^21 - 1이고요.

delete한 메모리 역시 2^21 - 1일 겁니다. 물론 java는 가비지 컬렉터가 있어서.. ㅎㅎ;;

결론적으로 보면, 뒤에다 추가하는 append 함수를 호출했을 때, 최악의 경우는 O(size)만큼이겠지만..

expand 연산은 2배씩 확장되기 때문에 뜸하게 일어납니다. 따라서 O(n)은 아니고요...

상환 복잡도로 분석하면 amortized O(1)임을 알 수 있어요. 그냥 저렇게 보이기만 해도 계속 append만 했을 때, append의 평균 복잡도는 O(1)이라는 걸 알 수 있어용..

혹여나 제 설명이 부족하다면.. 쉬운 자료 하나 첨부해 드리겠습니다.

https://hcn1519.github.io/articles/2017-05/amortized_analysis

"최악의 경우" 라는 키워드를 주목해 보세요. 저 글에서도 "최악의 경우" 라는 키워드에 굵게 표시되어 있습니다.

친절히 설명해주셔서 너무 감사합니다 ㅎㅎㅎㅎㅎ

많은 도움이 됐습니다!