[자료구조] 빅오 표기법(Big-O notation)

빅오 표기법은 알고리즘의 시간 복잡도를 나타내는 표기법이다.

O(f(n))으로 나타낸다.

 

알고리즘의 복잡도는 시간 복잡도, 공간 복잡도 두 가지로 구분할 수 있다.

 

시간 복잡도는 알고리즘 내 연산의 횟수와 관련이 있다.

알고리즘에서의 시간 복잡도라는 것은 'n값의 증가에 따른 처리 시간의 증가 정도'라고 할 수 있다.

쉽게 생각하면 루프를 몇 번 도는지, 재귀함수를 몇 번 실행시키는지로 볼 수 있다.

 

빅오 표기법에서는 재밌는 부분이 있다.

for i in 0..<10 {
	print(i)
}

for i in 0..<10 {
	print(i)
        print(i)
}

상단의 코드는 루프를 돌면 총 10번을 실행하게 되고 숫자 10 대신 20이 들어가면 20번, 30이 들어가면 30번을 돌게되므로
빅오 표기법으로 O(n)으로 표기할 수 있다.

 

그렇다면 하단의 코드는?

루프는 위와 동일하니 O(n)인데 출력을 두 번씩 실행하면 O(2n)이 아닌가?

하지만 동일하게 O(n)으로 표기된다.

 

이는 빅오표기법에서의 두 가지 특이점인 상수항 무시, 영향력 없는 항을 무시한다는 특성 때문이다.

 

상수항 무시

O(2n) -> O(n)

O(n^2 + 2) -> O(n^2)

 

영향력 없는 항을 무시

O(n^2 + n) -> O(n^2)

O(n + log n) -> O(n)

 

위와 같이 상수항은 제거함으로 최대한 간결한 표기를 한다.

 

일반적으로 사용하는 빅오 표기법에서의 우선 순위는 아래와 같다.

 

이미지 출처 : https://en.wikipedia.org/wiki/Big_O_notation

O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ) < O(n!) < O(nⁿ)

 

 

아래의 이미지들을 확인하기 전 참고해야하는 추가적인 부분들이 있다.

 

최선의 경우, 최악의 경우, 평균의 경우를 분석할 때 상한(O), 하한(Ω), 평균 수행 시간(Θ)을 구하려 한다. 앞의 예에서 알 수 있듯이, 주어진 함수(알고리즘)가 상한(O)과 하한(Ω)을 가진다고 해서 평균 수행 시간(Θ)이 항상 가능한 것은 아니라는 것이 분명하다. 예를 들어 어떤 알고리즘의 최선의 경우를 논의한다면 상한(O)과 하한(Ω)과 평균 수행 시간(Θ)을 구하려 하는 것이다. 이 장의 나머지 부분에서는 상한(O)에 집중할 텐데 왜냐하면 알고리즘의 하한(Ω)을 아는 것은 실용적으로 중요하지 않으며 상한(O)과 하한(Ω)이 같을 경우에는 세타 표기법을 사용하기 때문이다.
– 다양한 예제로 학습하는 데이터 구조와 알고리즘 for Java. 1장. 15쪽.

 

상한의 경우 빅-오, 하한의 경우 빅-오메가, 평균 수행 시간의 경우 빅-세타 라고 읽는다.

각 이미지에서 이 부분을 참고하길 바란다.

 

이미지 출처 : https://www.bigocheatsheet.com/

상단 이미지는 여러 자료구조 내에서 최적의 시간 복잡도로 풀이를 할 수 있는지 도움이 될 수 있는 자료다.

알고리즘 문제 풀이 뿐만 아니라 실제 프로그래밍에서도 큰 도움이 될 것 같다.

 

 

이미지 출처 : https://www.bigocheatsheet.com/

상단 이미지는 배열에서의 여러 정렬을 할 때의 시간 복잡도다.

추가적으로 각 정렬은 어떻게 이뤄지는지 등에 대한 포스팅을 해볼 생각이다.

 

 

참고한 사이트

https://johngrib.github.io/wiki/big-O-notation/

빅 오 표기법(Big O notation)

https://www.bigocheatsheet.com/

Big-O Algorithm Complexity Cheat Sheet (Know Thy Complexities!) @ericdrowell

https://cjh5414.github.io/big-o-notation/

빅오 표기법 (Big-O Notation), 시간 복잡도, 공간 복잡도

https://holika.tistory.com/entry/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%EB%B9%85%EC%98%A4-%ED%91%9C%EA%B8%B0%EB%B2%95Big-O-notation%EC%9D%B4%EB%9E%80

[자료구조] 빅오 표기법(Big-O notation)이란?