가. Big-O 표기법이란
•
Big-O 표기법이란 알고리즘의 성능을 수학적으로 표현하는 방법
•
시간적 공간적 복잡도를 알 수 있음
•
알고리즘의 성능을 예측하는 도구임
•
Big-O 표기 시 계수와 상수는 버림
아래 예제의 경우 2n에서 계수인 2는 버리고 O(n)으로 표기함
public int testMethod(int n){
for(int i = 0; i < n: i++) System.out.println(i);
for(int i = 0; i < n: i++) System.out.println(i);
}
Java
복사
나. O(1)
•
데이터의 크기에 상관없이 처리시간이 일정한 알고리즘
•
ex) index의 값이나, testArray의 값이 달라져도 처리속도는 변하지 않음
// 단, index는 testArray의 범위 내의 유효한 수
public int testMethod(int[] testArray, int index){
return testArray[index];
}
Java
복사
다. O(n)
•
입력 데이터의 크기에 비례하여 처리시간이 늘어나는 알고리즘
•
일반적으로 반복문에 해당함
•
ex) testArray의 길이가 커질수록 처리시간 비례하여 늘어남
public int testMethod(int n){
for(int i = 0; i < n: i++) System.out.println(i);
}
Java
복사
라. O() vs O(nm)
•
둘 다 이중 반복문에 해당함
•
O()의 경우 같은 변수에 대해 이중반복하는 경우
public int testMethod(int n){
for(int i = 0; i < n: i++) {
for(int j = 0; j < n: j++){
System.out.println(i + j);
}
}
Java
복사
•
O(nm)의 경우, 서로 다른 변수에 대해 반복문이 겹치는 경우
public int testMethod(int n, int m){
for(int i = 0; i < n: i++) {
for(int j = 0; j < m: j++){
System.out.println(i + j);
}
}
Java
복사
마. O()
•
처리할 데이터가 순차적으로 M의 곱만큼 증가하는 알고리즘에 해당
•
피보나치 수열의 경우 O()로 표기할 수 있음
1 → 2 → 4 → 8 → 16 ...
// 재귀함수 활용
public int Fibonacci(int n) {
if(n <= 1)
return 1;
else
return Fibonacci(n-1) + Fibonacci(n-2);
}
Java
복사
바. O(log n)
•
처리할 데이터가 순차적으로 반씩 줄어드는 알고리즘에 해당
•
이진검색이 대표적인 예
사. O(sqrt(n))
•
square root: 제곱근
•
n = 16(==4^2), sqrt(n) = 4
•
n = 9(==3^2), sqrt(n) = 3
Reference
•
Big-O, 엔지니어 대한민국, https://www.youtube.com/watch?v=6Iq5iMCVsXA