배열

C 배열과 파이썬 리스트 차이

C배열 : 메모리에 값자체를 연속적으로 저장한다

파이썬 리스트 : 메모리에 레퍼런스를 저장하고 이 레퍼런스는 다른 값들을 가르킨다.

 

💡 배열에서 값을 받아오거나 저장하는건 램의 특성으로 O(1)으로 접근 가능하다.

 

 

배열탐색

선형 탐색이라고도 불리며 인덱스 0번부터 차례대로 배열을 살펴본다.

⇒ 즉, 탐색은 O(n)이 걸린다.

 

정적 배열 : 크기가 고정된 배열

 

동적 배열 : 크기가 변하는 배열

• 정적 배열로 만들어진 자료 구조
• 정적 배열의 크기를 상황에 맞게 조절한다.

 

동적 배열 연산

추가연산

1. 정적배열에 남는 공간이 있을때 O(1)
2. 정적배열이 꽉찼을 때 : O(n)

분할 상환 분석

연산을 n번 했을 때 총 드는 시간 X를 n으로 나눠주는 할부 개념

⇒ 최악의 경우로 시간 복잡도를 얘기하는 것이 비합리적인 경우 사용

 

삽입연산

1. 정적배열에 남는 공간이 있을때 O(n)
2. 정적배열이 꽉찼을 때 : O(n)

⇒ 즉, 삽입 연산은 O(n)

 

삭제연산

1. 맨앞의 데이터를 지울 때 O(n)
2. 맨뒤의 데이터를 지울 때 O(1)