[자료구조]기본2_배열

 

 

배열

값을 저장하는 것이 아닌, 래퍼런스(주소)를 저장

그렇기때문에 큰값을 저장해도 무방(주소만 저장하기때문)

 

배열접근(주소를 알고있음)

저장 : 연속적으로 저장됨 O(1)

가져오기 : 인덱스값으로 계산하여 가져옴( O(1)로 가져옴_메모리의 특성을 이용)

 🙋‍♀️ 휘발성 정보인 RAM에 값을 저장하고, 가져온다. 그 속도가 빠른이유는 주소를 알고 있기 때문

 

배열탐색(주소모름)

선형탐색 : 순서대로 확인 O(n)

 

배열종류

• (정적)배열 : 크기가 정해진배열, 수정불가     ex) C언어 배열
• 동적배열 : Dynamic Array 크기변경가능, 수정가능   ex) Python
  • ➕동적배열의 추가방법[배열이 모두 차면 알아서 늘려줌]
    • 2배크기 자리마련 -> 기존데이터를 복사 후 추가 
    • ⏰시간복잡도 : 빈공간있을때(최고) -O(1) / 빈공간없을때(최악) -O(n)

 

분할 상환 분석 Amortized Analysis(할부개념)

시간복잡도를 다르게 계산하는 방법(시간복잡도를 최악의 상황으로 보는게아닌 평균을 내서 보는것)

최악의 경우보다는 최고(시간이 오래안걸리는)의경우가 많다.(배열내부에 빈공간이 있는경우가 더 많다)

그렇기때문에 동적배열의 시간복잡도를 O(n)으로만 생각하는건 비효율적이다.

 

최악의경우 분석 vs 분할상환분석

분할상환분석의 시간복잡도가 항상 줄어드는건아니다.

최악의경우분석과 비교해봤을때 더 적을때만 분할상환분석을 사용한다.

📌동적배열추가(append)연산은 최악의 경우 O(n) / 분할상환분석을 하면 O(1)걸린다

 

 

동적배열

삽입연산

• 최고(맨뒤) : O(1) -추가(append)
• 최악(맨앞) : O(n) -삽입(insert)

삭제연산

• 최고(맨뒤) : O(1) 
• 최악(맨앞) : O(n) -하나씩 당겨와야함

동적배열 축소하기

동적배열이 꽉 찬경우 2배로 늘리듯이, 배열에서 일정한 수 이하로 줄어들면 배열도 축소해야한다

보통 원래의 배열길이에서 1/3로 줄면 배열이 축소된다

• 최고(맨뒤) : O(1) 배열길이가 9일때 9->8로 줄어드는경우
• 최악(맨앞) : O(n) 배열길이가 9일때 4->3으로 줄어드는경우(1/3이하로 줄어드니, 짧은배열을 재정의후 옮김)

 

 

 

 

 

 

[출처] : 코드잇 - 자료구조