void function(int[] n) {
System.out.println(n[0]);
}
해당 메소드는 배열 n의 크기와 상관없이 단 한번의 결과를 반환한다.
이 알고리즘의 시간 복잡도는 O(1)이다.
void function(int[] n){
for(int i : n) {
System.out.println(n[i]);
}
}
해당 메소드는 배열 n의 크기만큼 반환 횟수가 늘어난다.
이 알고리즘의 시간 복잡도는 O(n)이다.
void function(int[] n) {
for(int i : n) {
for(int j : n) {
System.out.println(n[i] + n[j]);
}
}
}
해당 메소드는 배열 n의 크기가 늘어날때마다 반환 횟수가 거듭해서 늘어난다.
이 알고리즘의 시간 복잡도는 O(n^2)이다.
void function(int[] n, int[] m) {
for(int i : n) {
for(int j : m) {
System.out.println(n[i] + m[j]);
}
}
}
해당 메소드는 배열 n과 m의 크기의 곱 만큼의 반환 횟수가 나오게 된다.
이 알고리즘의 시간 복잡도는 O(nm)이다.
n과 m의 크기가 같다면 O(n^2)와 같은 시간 복잡도를 가진다.
void function(int[] n) {
for(int i : n) {
for(int j : n) {
for(int k : n){
System.out.println(n[i] + n[j] + n[k]);
}
}
}
}
해당 메소드는 배열 n의 크기가 늘어나는 크기의 세제곱만큼 반환 횟수가 늘어난다.
이 알고리즘의 시간 복잡도는 O(n^3)이다.
void binarySearch(int key, int n[], int low, int high) {
int mid;
while(low <= high) {
mid = (low + high) / 2;
if(key == arr[mid]) {
System.out.println(mid);
} else if(key < arr[mid]) {
high = mid - 1;
} else {
low = mid + 1;
}
}
return -1; // 탐색 실패
}
해당 메소드는 배열에서 특정 숫자의 위치를 찾는 방법 중 이진탐색(=이분탐색, binary search)이다. 이진탐색의 횟수는 배열 n의 길이가 1이 될때까지 2로 나눠지는 횟수와 동일하다. 횟수를 K라고 하고 이를 수식화 하면 log_2(n) = k
가 되고, 이를 시간복잡도로 나타낸 것이 O(log n)이다.
위에서 익힌 특정 시간복잡도들은 표를 통해 쉽게 비교해볼 수 있다. O(1)가 가장 빠를 확률이 높고, O(n!)가 가장 느릴 확률이 높은것을 확인할 수 있을 것이다.
참고 문서
엔지니어대한민국 - [자료구조 알고리즘] 빅오(Big-O)표기법 완전정복