가장 높은 차수로 표현합니다.
공간 복잡도도 이로 표현할 수 있지만 주로 시간복잡도를 나타낼 때 씁니다.
O(1), O(n), O(n^2), O(nlogn) ....
Array는 공간이 처음부터 정해진 만큼 할당이 됩니다. 그래서 공간이 너무 남아서 낭비되거나 모자라는 문제가 생길 수 있습니다. 반면에 링크드 리스트는 Node를 동적으로 생성해서 연결하기 때문에 추가/삭제가 편리합니다.
Array는 인덱스로 바로 접근할 수 있어서 빅오 표기법으로 O(1)의 효율을 가집니다. 반면에 Linked List는 접근할 때 O(n)의 효율을 가집니다.
배열이 끝에서만 데이터를 접근할 수 있는 선형 자료구조
Stack은 배열 인덱스 접근이 제한된다고 볼 수 있다.
LIFO : Last In First Out (후입 선출)
스택은 DFS에서 유용하게 사용된다.