빅오 Big(O)

 

Big O 표기법(Big-O notation)은 코드가 얼마나 효율적으로 수행되는지에 대해 수학적으로 계산해서 나타내는 수치입니다.

코딩인터뷰 단골질문!

 

빅오표기법은 시간 복잡도와 공간 복잡도를 나타내는데에 쓰입니다.

 

시간복잡도(time complexity) - 해당 코드가 실행되는 데에 걸리는 시간

공간복잡도(space complexity) - 해당 코드가 실행될때 메모리를 차지하는 정도를 나타냄

 

 

---

시간 복잡도를 표기하는 3가지 방식

Ω(omega) 해당 코드의 최상 실행시간

θ(theta) 평균 실행시간을 뜻함

O(omecron) 최악 실행시간

 

그러므로 Big-O는 항상 최악케이스에 해당합니다.

평균빅오는 몇이냐, 최상의 빅오는 잘못된 표현.

 

 

---

 

빅오 표기법

 

연산수가 적을수록 효율적이라고 판단된다.

n은 입력받은 값의 크기를 나타냄.

 

1. O(n)

proportional

입력값과 실행시간이 비례하다.

 

2. O(n^2)

loop within a loop

이중포문같은 경우 해당되는 표기법.

 

3. O(1)

Contstant

입력값에 상관없이 실행시간이 동일하다.

Big-O 중에 제일 효율적이다.

 

4. O(log n)

divide and Conquer

연산이 한번 실행될 때마다 연산되는 데이터가 절반씩 감소한다.

 

 

 

---

Big-O 간단표기법 규칙

1. 상수제거

반복문이 두번 실행되는 코드가 있더라도 2n으로 표기하지 않고 n으로 표기합니다.

 

2. 영향이 미비한 항 제거

이중포문 뒤에 일반 포문이 있는 경우 원래대로라면 O(n^2 + n) 으로 나타내는 게 맞아 보이지만,

n의 값이 커질수록 혼자있는 n의 영향은 미비해지기 때문에 표기하지 않습니다.

 

 

 

---

 

두 개 다른 인풋의 경우

O(n)이라고 표기 불가.

o(a+b) o(a*b)

 

 

 

 

---

https://www.bigocheatsheet.com/