728x90
Big-O 표기법 이란?
알고리즘의 성능을 수학적으로 표현하는 표기법으로 시간복잡도(Time Complexity), 공간복잡도(Space Complexity)를 표현할 수 있다. 이 때 상수는 무시한다.
표기법
1. O(1)
입력 데이터의 크기에 상관없이 언제나 일정한 시간이 걸리는 알고리즘
F(int[] n) {
return (n[0] == 0)? true:false;
}
그래프로 나타내면 아래와 같다.
2. O(n)
입력 데이터의 크기에 비례해서 처리시간이 걸리는 알고리즘
F(int[] n) {
for i = 0 to n.length
print i
}
그래프로 나타내면 아래와 같다.
<주의>
O(2n) => O(n) 으로 표기한다
빅오 표기법은 실제 알고리즘의 러닝타임을 재기 위해 만든게 아닌 장기적으로 데이터가 증가함에 따른 처리시간의 증가율을 예측하기 위한 표기법이기 때문에 상수는 무시한다.
F(int[] n) {
for i = 0 to n.length
print i
for i = 0 to n.length
print i
}위 코드를 보면 루프가 두 번 돌지만 중첩되어 도는 것이 아니라 각자 돌기때문에 O(2n)이지만 상수는 무시하고 O(n)으로 표기한다.
3. O(n²)
F(int[] n) {
for i = 0 to n.length
for j = 0 to n.length
print i + j;
}
그래프로 나타내면 아래와 같다.
4. O(n³)
F(int[] n) {
for i = 0 to n.length
for j = 0 to n.length
for k = 0 to n.length
print i + j + k;
}
그래프로 나타내면 아래와 같다.
>>나머지 표기법에 대해서는 공부하고 이해하고 써먹을 때마다 정리할 예정
728x90