[자료구조]Array와 Time complexity(searching, insertion, deletion)

Time complexity

• 실제 소요 시간보다는 단계의 개념에 더 가깝다고 볼 수 있음
• 단계가 적을 수록 효율적인 알고리즘

array

• 컴퓨터에 미리 메모리 공간을 예약하여 어느 정도 길이가 될 것인지 설정해야 하는데, python이나 javascript와 같은 경우 그 과정을 IDE내에서 알아서 진행해 줌
• 메모리 공간에 나뉘어진 여러 address에 value들이 할당됨
• index를 통해 메모리공간의 value에 접근 가능
  ex)

indexing

• 직접 index값을 통해 접근
  $O(1)$

Searching

• array내에 원하는 값을 찾는 과정
• array의 경우 Linear Search라고 부름
• $O(N)$

insertion

• 맨 끝쪽 index에 삽입할 경우 $O(1)$

    append()

• 중간에 삽입 시 $O(N)$ (모든 배열의 주소를 이동시켜야 함)

deletion

• 맨 끝쪽 index에서 제거할 경우 $O(1)$

    pop()

• 중간에 제거 시 $O(N)$ (모든 배열의 주소를 이동시켜야 함)

😝결론

• array는 직접 indexing하는 것외에 searching, insertion, deletion 등은 시간이 오래걸릴 수가 있음.
• set, dict, queue 등의 자료구조를 활용하여 효율적인 알고리즘을 설계할 수 있음

Reference

• https://youtu.be/NFETSCJON2M