[Python Data structure ] 배열 - insertion operation 시간복잡도 분석

<삽입 연산 - insertion operation 시간 복잡도 분석>

• appen는 동적 배열의 끝에 요소를 추가해주는 반면 insertion은 원하는 위치에 요소를 삽입한다.

추가 연산의 시간 복잡도

appen와 마찬가지로 아래 두 경우로 볼 수 있다.

1. 경우1 : 정적 배열에 남는 공간이 있을 때 :
   • 배열 중간에 새로운 요소를 넣을 경우, 가장 뒤의 요소부터 insertion 할 위치까지의 요소들을 하나씩 뒤로 밀어준다. 그 후 빈 공간에 요소를 저장한다.
     

     

• 시간 복잡도 : 최악의 경우
• index 0에 요소를 추가할 경우엔 모든 index를 하나씩 뒤로 밀어주게 된다. index로 요소에 접근하는 경우 O(1)이며 n번 반복하므로 O(n)이 된다.
  
  

  

2. 경우 2 : 정적 배열이 찼을 때 :
   • 새로운 배열을 만든 후 기존 데이터를 복사하여 저장한다. 그 후 위와 비슷하게 인덱스를 뒤로 밀고 요소를 추가한다.
   • 시간 복잡도 원하는 위치 뒤에 있는 모든 요소들은 뒤로 밀어주는 경우 : O(n)
   • 마지막으로 새로운 데이터를 저장 : O(1)
   • 새로운 배열을 만들고, 기존 배열을 복사하는 작업의 시간 복잡도 : O(n)

⇒ O(n) + O(n) + O(1) ⇒ O(n)

삽입 연산은 경우 1과 경우 2가 O(n)으로 같다.

결론 : 삽입 연산의 시간 복잡도 : O(n)