목록컴퓨터공학 (1)

사진과 음악을 좋아하는 개발자 지망생의 블로그

배열 or 리스트(정적 배열, 동적 배열, doubling, 분할 상환 시간 복잡도), 연결리스트(Linked List), 파이썬 리스트(특징, 메모리 구조, 주요 연산 시간 복잡도)

1. Array미리 할당된 공간에 연관된 데이터를 연속적이며 순차적으로 저장하는 자료구조1) 정적 배열(Static Array)미리 할당된 크기를 가지며 연속적으로 순차적으로 데이터를 저장하는 자료구조특징고정된 크기를 갖는다저장 공간을 미리 확보해야 한다메모리 상에 데이터가 서로 인접한(연속적인) 메모리 위치에 저장된다 → 논리적 저장 순서와 물리적 저장 순서가 같다시간 복잡도삽입과 삭제 → 삽입 및 삭제로 인해 데이터들이 한칸 씩 움직여야 하기 때문에 $O(N)$을 갖음탐색메모리 시작 주소에 + N 만 하면 되기 때문(랜덤 접근, Random Accesss)에 시간 복잡도 $O(1)$을 갖음Random Access(Direct Access)데이터 접근 시, 어떤 순서로든, 어느 위치에 있는 데이터라도 ..
CS/자료구조 & 알고리즘 2024. 12. 12. 08:28
이전 Prev 1 Next 다음