-
[개념] BigO 표기법알고리즘 2023. 11. 6. 22:55
빅오표기법이란?
우리는 알고리즘 문제를 풀던 코드를 짜던 무엇이 가장 효율적인지 시간상 짧게 걸리는지를 확인 할 필요가 있다.
( 성능과 직접적으로 연결되는 부분이기 때문 )
빅오표기법
상수시간 알고리즘(Constant Time Algorithm)
- 가장 이상적인 알고리즘으로써 실행되는 횟수가 상수값으로 나타나서 그 횟수만큼만 실행을 하기때문에 Input되는 데이터가 어떻든 같은 시간안에 처리하게 된다.
const array = [1, 2, 3, 4, 5] const fnc = (array) => { console.log(array[0]) }
만약 아래 코드와 같이 출력하는 값이 여러개로 늘어난다하더라도 상수는 제외하고 나타내기 때문에 결국은 O(1)으로 표기된다.
const array = [1, 2, 3, 4, 5] const fnc = (array) => { console.log(array[0]) // 1번 console.log(array[0]) // 2번 console.log(array[0]) // 3번 }
O(N)
- 위의 상수시간 알고리즘과 동일하게 상수는 표현하지 않고 Input의 크기에 정비례하여 step이 증가하는 알고리즘
const array = [1, 2, 3, 4, 5, 6] const func = (array) => { for (i of array) { console.log(i) } }
O(N^2) ...
- step의 증가량이 굉장히 비효율적으로 증가하는 알고리즘으로써 이중반복문 이상의 것들이 이러한 모습을 나타낸다.
const array = [1, 2, 3, 4, 5, 6] const func = (array) => { for (i of array) { for(j of array) { console.log(j + i) } } }
O(log N)
- 이진검색 알고리즘에서 보였던 모습을 나타낸 것으로 정렬된 input에서만 사용할 수 있는 제한적이지만 효율적인 알고리즘
이진검색 알고리즘에서 input의 크기가 2배가 되어도 step의 수는 1번이 늘어나는 것을 생각하면 된다.
'알고리즘' 카테고리의 다른 글
[프로그래머스 1단계] 신고 결과 받기 (0) 2024.01.29 [프로그래머스 1단계] 성격 유형 검사하기 (0) 2024.01.26 [개념] 검색알고리즘 (선형 VS 이진) (1) 2023.11.04 [개념] 유클리드 호제법을 통한 최대공약수 + 최소공배수 (0) 2023.11.02 [프로그래머스 알고리즘] 2중반복문 (0) 2023.06.22