상환입력시간

상환입력시간

상환입력시간이란?

• 참고: https://zeddios.tistory.com/60
• 최악의 경우에 대해 최악의 경우가 발생하도록 연속된 연산을 수행하고, 그때의 한번의 연산에 대한 평균 수행시간 분석

ArrayList에 원소 추가요~

• ArrayList에 원소를 추가하는건 O(1)일까?

• O(N)의 시간복잡도로 원소가 추가되는 경우가 있어
  • 이때는 할당한 배열에 더 집어넣을 곳이 없는경우
  • 이때는 기존의 배열보다 2배의 사이즈로 배열 키워서 기존 원소 복붙
  • 이러면 O(N) 만큼의 시간이 듬
  • 이때가 아니라면 O(1)이 맞음

• 그러면 평균을 내보자고
  • 리사이징을 시키는 N개의 원소를 집어넣을때까지...
  • O(1) + O(1) + O(1) + ... + O(N) 이라고 하면
  • ((N-1) + N / N) 으로 평균시간을 퉁칠수 있겠지?
    • 이러면 시간 복잡도 여전히 O(1)이 되시겠습니다!

• StringBuilder 도 마찬가지야!
  • 가변크기 배열을 이용해서 필요한 경우에만 문자열을 복사하도록 함!