컴퓨터 시스템에서 메모리를 word 단위로 관리한다.
32bit system -> word = 32bit
64bit system -> word = 64bit
sequence - extrinsic order
set - intrinsic order
Big-O
아무리 늦어도 이것보단 빠르다.
Big-Omega
아무리 빨라도 이것보단 느리다.
Big-Theta
최선의경우, 최악의 경우 모두 만족
Static array
- 메모리 크기가 변화하지 않는다
- 컴파일단에서 메모리가 할당되기 때문에 지역변수일 경우 Stack에 할당. 전역인 경우 BSS나 데이터 섹션에 할당
- 새로운 크기의 배열이 필요한 경우 새로운 크기의 메모리를 다시 할당해야한다.
Dynamic array
- 메모리 크기가 변화한다.
- 런타임에 크기가 정해지기때문에 heap에 할당된다.
- 새로운 크기의 배열이 필요한 경우 2배정도 (언어마다 다름. 파이썬은 2배, 자바스크립트 1.5배정도?) 크기를 미리 만들어서 할당하기 때문에 static array에 비해 insert에서 static array에 비해 성능이 좋다. (amortized time - 상수시간)
