<시간 복잡도>
프로그램의 연산자의 개수로 계산
1. 상수 개의 연산자 : O(1) ... 처리할 자료 개수 n개에 영향받지 않음.
ex) 산술 연산자, 변수 할당, 인덱스를 사용한 배열 요소로의 접근이나 키를 이용한 객체 요소로의 접근,
2. 계수 x의 크기에 상관없이 xn 개의 연산자 : O(n) => 빅오 표현식의 단순화 ... ex) 반복문 but 반복문 조건에 따라 다름 !
3. 계수 x의 크기에 상관없이 x*n*n 개의 연산자 : O(n^2) => 빅오 표현식의 단순화, 최고차항 ... ex) 중첩(nested) 반복문
<공간 복잡도>
입력(n)이 커질수록 알고리즘이 얼마나 얼마나 공간을 많이 사용하게 되는지
cf. 보조 공간 복잡도(auxiliary space complexity) : 입력(n)은 제외하고 알고리즘 자체가 필요로 하는 공간을 의미
ㅡ JS에서 booleans, numbers, undefined, null은 불변 공간이다. => 입력 크기(n)와 상관 없음, O(1) 공간 필요
ㅡ 문자열은 문자열의 길이가 입력 크기(n)이 되어 O(n) 공간이 필요하다.
ㅡ 참조 타입인 배열이나 객체는 배열의 길이나 객체의 키 개수가 입력 크기(n)이 되지만,
그 길이나 키 개수와 상관없이 새로 만들어지는 원시 타입 변수의 개수가 상수개가 되면
배열이나 객체와 관련된 함수라 하더라도 보조 공간 복잡도는 O(1)이다 !
<로그(Logarithms)>
나눗셈과 곱셈을 쌍으로 생각하듯이, 로그함수와 지수(exponent)함수는 쌍으로 생각해야할 개념이다.
어떤 탐색 알고리즘들, 효율적인 정렬 알고리즘들, 재귀 알고리즘은 로그 시간 복잡도를 갖고 있다.
빅오로 측정되는 알고리즘의 시간과 공간 복잡도는 하드웨어에 영향을 받지 않는다 !
빅오는 알고리즘들을 서로 비교할 수 있는 성능 측정의 단위로 기능한다 !
빅오 관점에서 객체와 배열을 살펴보자.
객체는 정렬되어 있지 않은 데이터 구조로 key와 value의 짝으로 저장되어 있다.
그래서 객체는 정렬되어 있을 필요가 없을 때, 빠른 접근과 입력& 삭제가 필요할 때 사용하는 것이 좋다.
입력과 삭제, 접근, 수정은 O(1) 즉 상수 시간이 걸리고,
탐색은 O(n) 시간이 걸리며 객체의 기본적인 연산은 매우 빠르다 !
예를 들어 객체의 자료 입력은 순서를 신경쓸 필요없이 키를 사용해 추가하기에 이 때의 시간복잡도는 O(1)이다.
객체의 메소드들 중
객체의 키들에 접근하는 Object.keys, 객체의 키의 값에 접근하는 Object.values, 객체의 키와 키의 값을 쌍으로 하는 배열요소를 가진 배열(2차 배열)을 반환하는 Object.entries는 O(n) 선형 시간이다.
키를 인수로 넣어주면 그 키가 객체 안에 존재하는지 아닌지만 알려주는 hasOwnProperty는 O(1) 상수 시간이다.
vs
배열은 인덱스(0 ~ )로 정렬되어 있는 데이터 구조이다.
그래서 빠른 접근과 입력, 제거가 필요할 때는 정렬되어 있는 것이 배열이 유용하지만, 연산하는 시간은 더 걸릴 수 있다 !
인덱스(객체의 키의 역할과 같음)로 바로 원하는 값에 접근이 가능하므로 객체처럼 접근은 O(1) 즉 상수 시간이 걸리고,
입력과 삭제는 경우에 따라 다른 시간복잡도를 가진다. 배열의 뒷 부분에 입력하거나 삭제할 때는 O(1)이 걸리지만,
배열의 앞쪽에 입력하거나 삭제할 때에는 인덱스를 전부 재설정해줘야 하는 일이 생겨 O(n)이 걸리게 된다. 배열의 앞쪽에 꼭 작업해야하는 경우가 아니면 되도록 피하는 게 좋겠다. 배열이 비어있을 때를 제외하면, push와 pop하는 작업이 shift와 unshift 작업보다 빠르다는 이야기이다.
탐색은 배열의 크기만큼 진행해야 하므로, O(n)이다.
배열의 메소드들 중
배열의 뒤쪽에 입력하고 삭제하는 push, pop은 O(1) 상수 시간이고,
배열의 앞쪽에 입력하고 삭제하는 shift, unshift, 두 배열을 합치는 concat, 배열의 일부나 전체를 복사해 가져오는 slice, 배열의 요소를 제거하거나 추가하는 splice, 배열을 정렬하는 sort, 배열을 순회하는 forEach, 배열의 요소들을 주어진 함수에 적용해서 결과값을 새로 반환하는 map, 주어진 함수에 해당하는 요소들을 새로 반환하는 filter, 배열의 요소들을 누적하여 하나의 결과값을 반환하는 reduce는 O(n) 선형 시간이다.
배열을 정렬하는 sort는 O(nlogn)이다. cf. 배열을 정렬하는 것은 요소를 한번씩 보는 것에 끝나지 않기 때문에 O(n)보다 크다.
'KDT TIL Note > 알고리즘' 카테고리의 다른 글
| [알고리즘 자습] 대표적인 데이터 구조: 해쉬 테이블(Hash Table) (0) | 2022.12.23 |
|---|---|
| [알고리즘 자습] 문제 해결 접근법 (0) | 2022.11.30 |
