빅오는 뭘까?

자료구조와 알고리즘

빅오 표기법

빅오 표기법은 알고리즘의 ‘효율성’을 평가하기 위한 분석

예를 들어, 아래와 같은 질문이 떠오를 수 있다.

1. 프로그램을 실행하여 알고리즘이 입력받는 변수가 n(최악의 상황)일 때의 소요시간이 얼마나 되는가?
2. n이 무한이라면?

다시 말해, 장기적으로 데이터가 증가함에 따른 처리시간의 증가율을 예측하기 위함이다.

성능은 아래와 같다.

예시: O(n)
// O(2n) => O(n) - 상수는 무시한다
// 만약 n이 5여도 5n -> O(n) - 상수는 제외
function test(n){
  for(let i = 0; i < n; i++>){
    console.log(i)
}

예시: O(n²)

function test(n){
  for(let i = 0; i < n; i++>){
    console.log(i)
    for(let j = 0; j<n>)
    console.log(i)
  }
}

빅오 표기법은 알고리즘의 시간 복잡도와 공간 복잡도를 나타내는데 주로 사용된다.

• 시간복잡도 - 실행시간

• 공간복잡도 - 공간 효율성 (메모리)

참조 @callmedevmomo

참조 brandon의 블로그

빅오메가는 하한선 세타는 상한과 하한 둘다