02. 알고리즘 복잡도
알고리즘 평가 지표
- 정확성
- 작업량
- 메모리 사용량
- 최적성
- 효율성 -> 시간복잡도, 공간복잡도
코딩테스트에서 중요시 할 것은 : 메모리 사용량 과 효율성 중에 시간복자도를 중요시 해야 한다.
메모리 사용량은 많이 주기 떄문에 문제에서는 시간복자도에 포커스를 두는 것이 좋다.
시간복잡도
- 입력 크기의 값에 대해 단위 연산을 몇 번 수행하는지 계산하여, 알고리즘의 수행시간을 평가하는 방법
- 3가지 접근적 표현법
- 빅오 : 최악의 상황을 고려하여 성능 측정 결과 표현(어떤한 상황이더라도, 이것보다 나빠질 수 없다는 케이스)
- 세타 : 평균적인 경우에서의 성능 측정 결과 표현 (평균적인 상황)
- 오메가 : 최선의 상황일 때의 성능 측정 결과 표현( 베스트 상황일때 이정도의 퍼포먼스가 나온다는 케이스)
빅오 표기법
for 문이 몇개로 중첩되어 있느냐로 간단하게
for문 하나당 n으로
for문이 2개 면 n2(n제곱)
1. O(1) - [오원]표기법
function big_o(n){
let sum = 0; // 1회
sum = n * 2; // 1회
return sum; // 1회
}
// 3회의 -> O(1)
// 상수를 가질떄는 아무리 커지더라도 상수이므로 o(1)로 표기즉, 반복문이 없고 단순의 일련의 코드들만 수행하는 경우에는 O(1)표기
2. O(N) - [오엔]표기법
function big_o(arr, n){
let sum = 0; // 1회
for(let i = 0; i < n; i++){
sum += arr[i]; // n회
}
return sum; // 1회
}
// n + 2회 -> O(N)
//기초 상수를 날리고 가장 높은 차수를 남기다
// O(N)표기가 된다.
// 빠른 축으로 볼 수 있다.3. O(N²) - [오엔제곱]표기법
많이 느린
n이 커지면 커질 수록 시간이 오래 걸리는 코드로 본다.
function big_o(arr,n){
let sum = 0; // 1회
for(let i = 0; i < n; i++){
for(let j = 0; j < n; j++){
sum += arr[i][j]; // n * n = n²
}
}
return sum; // 1회
}
// n² + 2회 -> O(N²)
//만약 , n² + n + 2 여도 O로 표기했을 때에도 O(N²)으로 표기가된다.
// ㅐ로 표기했을 때, 가장 높은 차수를 남기고 나머지는 날리기 때문4. O(log N) - [로그엔] 표기법
병합정렬, 분할정복할때 문제에 많이 사용한다.
log가 많으면 많을 수록 특정이상 안올라가기 떄문에 O(N)보다 더 빠른 알고르리즘을 갖고 있다.
function big_o(n){
let sum = 0; // 1회
for(let i=0; i<n; i *=2){ // N/2회
sum+=2;
}
return sum; // 1회
}
// N/2 + 2 -> O(log N)
// N/2 + 2 를 O로 표기했을 때, 나는기 어떤 것이든 log로 치환이 되면서 O(log N)로 표기된다.결론
for을 중첩할 수록, n이 증가 하면 증가할 수록 속도가 커지기 때문에 이런한 것들은 지양해야 한다.
참고
1. Data Structure Operations
접근, 찾기, 삽입, 삭제에 대한 평균적인 케이스의 얼마만큼 시간 복잡도가 드는지 정리한 도표
실제 어떠한 상황에서 어떤 데이터 structure를 사용해야 할지 파악하는데 참고가 되는 도표
결국 Hash Table이 O(1)만큼의 시간복잡도를 가지기 때문에 현업에서도 많이 사용하고 있는 알고리즘이다.
또한, Array, Stack, Aueue, Singly-Linked List, Doubly-Linked List, B-Tree, Red-Black Tree도 많이 사용하는 structure라고 할 수 있다.
2. Array Sorting Alogrithms
정렬에 있어서도, 오름차순, 내렴차순 등 정렬할때 수 많은 방법이 있는데 각각 시간이 다르기 떄문에
best와 worst를 볼 수 있는 도표이며, 실제로 시간 복잡도와 공간복잡도가 각각 다르게 나타난다는 것도 볼 수 있는 도표이다.