출처 : https://www.youtube.com/watch?v=NFETSCJON2M&list=PL7jH19IHhOLMdHvl3KBfFI70r9P0lkJwL&index=3

1. 시간복잡도란?

---

• 데이터 구조의 오퍼레이션 혹은 알고리즘이 얼마나 느리고 빠른지 측정하는 것
• 실제 시간을 측정하는 것이 아니라 얼마나 많은 단계[steps]가 있는가로 측정
• 단계가 적을수록 좋은 것
• 5 step > 20 step

2. 메모리 관점에서 배열이 어떻게 보일까?

---

✨ 메모리의 종류

1. volatile(휘발성) 메모리 : RAM, 컴퓨터를 껐다 키면 데이터가 사라짐

• 프로그램이 돌아가고, 변수를 생성 할 때, RAM에 저장
• RAM(Random Access Memory) : 하드 드라이브보다 데이터 읽는 것이 빠르며, 데이터 접속을 랜덤으로 가능

001	002	003
004	005	006
007	008	009
010	011	012

• 위와 같이 RAM이 데이터를 넣은 박스라고 생각해보면 프로그램이 RAM에게 006으로 가주세요 하면 랜덤하게 접속 가능하기에 데이터를 읽는 것이 빠른 것, 바로 이동 가능(순차적으로 가는 것이 아니기 때문)
  
  

2. non-volatile(비휘발성) 메모리

• 하드 드라이브 같은 것, 컴퓨터를 껐다 키면 데이터가 사라지지 않음
• 즉, 메모리 관점에서 배열을 만들때, 컴퓨터에게 이게 얼마나 긴지 설명해야 함
• 나의 배열은 4개 만큼 길어 미리 예약/할당해줘! 메모리 안에서 박스들이 나란히 위치할 수 있게
• 배열은 검색, 추가,삭제시 느려짐

3. 배열

---

✨ Reading : O(1)

요소	“pasta”	“pizza”	‘ice cream”	“potato”

메모리 주소 001 002 003 004

index 0 1 2 3

• 위치만 알면, 배열의 데이터에 접속 가능 ⇒ 배열에서 읽어내는 것이 빠름, 컴퓨터는 배열이 어디서 시작되는 지 아니까
  
• EX. 피자를 원하면 컴퓨터에게 인덱스 1번의 값을 달라고 하면 됨
• 많은 자료를 읽어내려면 배열이 Good, 배열의 요소의 개수 상관없이 Random 하게 읽어내니까
• 배열에서 요소에 접근하거나 값을 변경하는 작업은 항상 입력 크기의 관계 없이 일정한 시간 내에 실행
• 예를 들어, 배열의 첫 번째 요소에 접근하거나 값을 변경하는 작업은 항상 고정된 시간만큼 걸린다.
• 이는 입력 크기에 관계없이 동일하게 빠르게 실행되며, 이러한 특성 때문에 배열의 Big O 표기법은 O(1)로 표현

✨ Searching : O(n)

요소	?	?	?	?

• 해당 값(=ex. 피자)가 배열에 있는지, 없는지 모름
• 어디에 있는지도 모르기 때문에 검색
• 하나하나 다 뒤져봐야 함
• So, 읽는 것보다 시간이 많이 걸림
• Random Access가 있어 주소를 찾아 박스에 쉽게 접근은 가능하나, 그 박스를 열어야 값을 확인 가능
• 배열의 아이템을 하나하나 열어보고 맞는지 체크하는 과정을 하나하나 해야함
• Linear Search[선형 검색] : 순서대로 0부터 끝까지 차근차근 찾는 것

✨ Insert[Add] 혹은 배열에 쓰기 : O(n)

“pasta”	“ice cream”	“pizza”	“potato”

• 만약, “tomato”를 넣고 싶다면, 미리 공간을 확보해뒀으니까 공간 걱정은 No!
• 결국 어디에 토마토를 추가할 것인가!
• 만약 중간이 앞에 추가하고 싶다면 나머지 값들을 옮겨야 함(아래와 같이)

“pasta”		“ice cream”	“pizza”	“potato”

• 근데 만약.. 공간이 꽉 차 있는데 값을 추가하면 배열의 길이는 정해져 있기 때문에 곤란
• ⇒ 해결방안 : 새로운 배열을 만들고, 그 배열에 이전 배열을 복사하고, 새로 추가해야 함
• 그래서 시간이 오래걸리고 복잡

✨ Delete : O(N)

배열에 뭔가를 추가하는 것과 비슷

배열을 이리저리 움직여야 함

“pasta”	“ice cream”	“pizza”	“potato”

EX. “ice cream”을 없애고 싶어 ⇒ 삭제 후 공간을 채우기 위해 앞으로 땡겨야 함

“pasta”	“pizza”	“potato”

4. 결론

---

• 배열의 통합적인 빅오는 배열의 각 연산의 최악의 경우(O(N))를 종합한 결과일 수 있다.
• 배열은 접근 연산을 제외하면 탐색, 삽입, 삭제 연산에 대해 비교적 효율적이지 않은 편이므로, 알고리즘을 설계할 때 이러한 연산의 효율성을 고려
• 오히려 데이터 추가 및 삭제는 연결 리스트가 더 빠르고 배열은 느림 배열은 모든 상자를 앞으로 옯겨야 추가가 가능하지만, 연결 리스트는 선을 바꿔서 연결해주기만 하면 되기 때문