선형 자료구조2 선형 자료구조 선형 자료구조- 데이터를 순차적으로 저장 (각 데이터가 1:1로 연결되는 방식)- 배열, 링크드 리스트, 스택, 큐배열연속적인 메모리 공간에 순차적으로 저장되는 자료구조 특징- 모든 요소가 같은 타입>>> 연속적인 메모리 공간에 데이터들이 존재하고, 데이터들의 타입이 같으니 O(1)로 시간 복잡도로 랜덤 접근 가능- Sequence와 Collection 프로토콜을 채택하고 있는 컬렉션 타입 Capacity- 새로운 저장공간 없이 배열이 포함할 수 있는 요소의 개수- 초기화 시점에 요소의 개수만큼 capacity 설정- capacity를 넘어가게 되면 기존 capacity의 약 2배 크기의 새로운 공간을 만든 후 기존 배열을 복사하고 요소 추가- reserveCapacity 메서드를 활용하여 불필요한 배열.. 2024. 12. 18. 자료구조 사전지식 1. 시간복잡도- 입력의 크기와 문제를 해결하는데 걸리는 시간의 상관관계 => 쉽게 이야기하면 내 코드가 연산되는 횟수 1-1. Big - O 표기법- 모든 경우를 고려했을 때 최악을 기준으로 시간복잡도 표현- 가장 큰 영향을 주는 요소를 기준으로 표현=> 상수항 무시=> 계수 무시=> 최고차망만 표시 But, 항상 시간복잡도가 크다고 해서 연산횟수가 많은 것은 아님=> 데이터의 크기에 따라 결정 1-2. 그 외 표기법- Big-Ω (빅 오메가): 최선의 시간 복잡도- Big-θ (빅 세타): 평균적인 시간 복잡도 2. 공간복잡도- 입력의 크기와 문제를 해결하는 데 필요한 공간의 상관관계 2-1. Bit & ByteBit- 0,1 을 표현하는 데이터 양의 최소 기본 단위Byte- 1byte = 8bit.. 2024. 11. 23. 이전 1 다음
