티스토리 뷰
big-o 의 필요성
알고리즘을 풀이하는데 수많은 해결법이 있는데 어떤 해결이 제일 괜찮은 해결인지 알려면 필요한 것이 빅오 표기법이다.
코드를 일반적으로 수치를 사용해서 비교하는데 사용.
왜 사용해야 되나? 알고리즘의 속도에 따라 성능이 좌지우지 되기 때문이기도 하고 면접에서도 물어본다
공간복잡도
입력되는것을 제외하고 알고리즘 자체가 필요한 공간
- 불린, 숫자, undefined, null : 불변 공간
- 문자열, 참조형, 배열, 객체: O(N) 공간 // 문자열의 길이 만큼
입력의 값에는 상관없이, 무조건 그냥 상수 두개 만큼의 공간만 있으면 됨
차지하는 공간은 입력된 배열의 크기와 비례해서 커짐
객체의 시간복잡도
이 객체에는 3쌍의 key value를 가지고 있음
객체는 정렬되어 있지는 않지만, 나머지 모든 부분(입력, 제거, key에 접근하는 시간) 에서 빠름 O(1)
키를 검색하는 거는 모든 키를 봐야되니 O(N)
자바스크립트에는 어떤 정보를 객체 안에 상수 시간안에 저장,수정, 삭제 할 수 있음 왜냐면 정렬되어 있지 않기 때문에 어디에 새로운 객체를 입력하든지 상관이 없기 때문 그냥 key를 가지고 저장
탐색은 key를 찾는것이 아님. 특정한 정보가 어떤 value에 있는지 알려면 모든 속성을 확인해야됨
객체와 함께 따라오는 메소드의 경우 객체의 이름을 치면, key 값의 배열이 돌아옴 -> 아이템의 수가 늘어나면서 각각 아이템들에 접근해서 배열에 추가해야되는 시간이 늘어남.
hasOwnProperty의 경우 원하는 속성을 전달하면, 해당 속성의 존재 유무만 돌려주면 됨으로 해당 키를 가지고 값만 확인 하면 되니 상수시간이 됨.
배열의 시간복잡도
배열의 경우 정렬이 되어 저장이 됨. 정렬된 데이터 구조는 싱글 리스트 정렬이나 더블 리스트 정렬 등등 배열 뿐만 아니라 다양한 구조가 존재함. 입력과 제거의 경우 배열이 오래 걸릴수있음. 접근은 빠음(객체와 동일)
입력과 제거는 어느 위치에 따라 다른 시간 복잡도를 가짐. 끝에 추가 하고자 하면 O(1)임. 그냥 추가하고 인덱스를 추가하는 것은 객체를 추가하는것과 동일. 하지만 시작에 추가/제거 하고 싶으면, 모든 인덱스를 하나씩 뒤로/앞으로 미뤄줘야됨. 즉, O(N)이 걸림. 맨 앞에 추가/제거(shift/unshift)는 맨 뒤 추가/제거(push/pop)보다 무조건 오래 걸림 (빈 배열을 제외하고)