🎯 목표 : 시간 복잡도의 개념 이해와 효율적인 시간 복잡도를 구현 할수 있어야 한다.
📒 시간 복잡도
📌 개요
- 입력값에 따라 증가하는 시간의 비율을 최소화한 알고리즘을 구성하기 위해서는 시간 복잡도를 고민해야한다.
- 시간 복잡도는 주로 빅-오 표기법을 사용한다.
- 빅-오 표기법은 최소한 특정 시간을 추정하는 표기법으로 상수들을 무시한다.
📌 Big-O 표기법
빠른 순서 ↑
- 상수 시간 = O(1)
- 로그시간 = O(log N)
- 직선형 시간 = O(N)
- 2차 시간 = O(n^2)
- 지수 시간 = O(A^n)
느린 순서 ↓
- 최악의 경우의 수를 고려해서 최소한 특정 시간을 추정하여 표현한 방법.
👉 O(1)
- 입력값이 증가하더라도 연산 시간은 증가하지 않는다.
- 아래 코드에서 이미 정의된 배열과 인덱스 값을 인자로 받는 메소드에서, 배열의 길이가 아무리 길더라도 인덱스 값으로 배열에 접근하기 때문에 반복 연산은 없다. 단 한번의 연산만 실행하기 때문에 시간 복잡도를 O(1) 으로 표기할수 있다.
public int O1_algo(int[] arr, int index) {
return arr[index];
}👉 O(n)
- 입력값이 증가함에 따라 연산에 필요한 시간이 비례하는 시간 복잡도.
- 아래 코드에서 3개의 반복문이 있으며 각 반복문당 n만큼의 반복을 하게된다.
- 아래 메소드의 시간 복잡도를 O(3n)으로 표기할수 있지만, 빅-오 표기법에서 변하지 않는 상수 3은 의미가 없기때문에 시간 복잡도 표기 할때 상수는 생략하고 O(n)으로 표기한다.
- 입력값이 커질수록 상수의 의미는 없어지기 때문에 생략한다.
public void On_algo(int n) {
for(int i = 0; i < n; i++) {
// do.....
}
for(int i = 0; i < n; i++) {
// do.....
}
for(int i = 0; i < n; i++) {
// do.....
}
}👉 O(n^2)
- 입력값이 증가함에 따라 시간이 n의 제곱으로 증가 한다.
- 아래 코드에서 2중 반복문이 실행될때 n만큼의 반복속에서 다시 n만큼의 반복을 하기 때문에 n의 2제곱으로 반복을 표현할수 있다. 만약 5 를 매개변수로 삽입하고 반복문은 1초마다 반복한다고 가정했을때, 외부 반복문이 1번 동작하면, 내부 반복문은 5번 동작하게 된다. 외부 반복문이 5번 동작하게 되면 5 x 5 = (5^2) 만큼의 시간이 흐르게 될것이다.
- 이를 시간 복잡도로 표기하게 되면 O(n^2)로 표기할수 있다.
public void Osquared_algo(int n) {
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
// do.....
}
}
}👉 O(2^n)
- 빅-오 표기법 중 가장 느린 시간 복잡도를 가진다. 반복할때 마다 총 반복 수가 두배로 늘어나기 때문이다.
- 대표적인 O(2^n) 시간 복잡도를 가지는 예제로는 해당 순서의 피보나치 수열을 구하는 알고리즘이 있다. 물론 피보나치 수열의 알고리즘도 메모이제이션 혹은 꼬리 재귀 방식으로 구현한다면 O(n) 시간 복잡도에 근사한 시간 복잡도를 가지는 알고리즘으로 구현할수 있다.
- 아래 코드에서 피보나치 수열을 구하기 위한 재귀 메소드를 구현했다.
- 자바 8의 JVM 에서는 꼬리 재귀 최적화 기능이 없기 때문에, 꼬리 재귀와 동일한 로직으로 구현했다.
public class RecursiveFunction {
public static void main(String[] args) {
System.out.println("30 th fibonacci Tail : "+fibonacciTail(30,0,1));
System.out.println("fibonacci Tail : "+ countFibTail);
System.out.println("30 th fibonacci : "+fibonacci(30));
System.out.println("fibonacci : "+ countFib);
}
public static int fibonacci(int number) {
countFib++;
if(number <=1) return number;
else return fibonacci(number-2)+ fibonacci(number-1);
}
public static int fibonacciTail(int input, int before, int after) {
countFibTail++;
if(input <=1) return after;
else return fibonacciTail(input-1,after,before+after);
}
}
// 출력값
// 30 th fibonacci Tail : 832040
// fibonacci Tail : 30 // O(n)
// 30 th fibonacci : 832040
// fibonacci : 2692537 // O(2^n)📒 Colletion 시간 복잡도
📌 Colletion
- 알고리즘 문제를 해결할때 큰 사이즈의 데이터를 Colletion으로 다룰때 정확한 시간 복잡도를 알고 사용하는 것이 중요하다.
👉 ArrayList
시간복잡도
add : O(1)
remove : O(n)
get : O(1)
Contains : O(n)
iterator.remove : O(n)
# 데이터 추가,삭제를 위해 임시 배열을 생성해 데이터를 복사
# 대량의 자료를 추가/삭제시 복사가 일어 나게 되어 성능 저하
# 데이터의 인덱스를 가지고 있어 데이터 검색시 빠름👉 LinkedList
시간복잡도
add : O(1)
remove : O(1)
get : O(n)
Contains : O(n)
iterator.remove : O(1)
# 데이터를 저장하는 각 노드가 이전 노드와 다음 노드의 상태만 알고 있다.
# 데이터 추가/삭제시 빠름
# 데이터 검색시 처음부터 노드를 순회하여 상대적으로 느리다👉 HashSet
시간복잡도
add : O(1)
contains : O(1)
next : o(h/n) h는 테이블 용량
# 중복 허용 안됨(Key)
# 순서없이 저장
# null을 허용한다.👉 LinkedHashSet
시간복잡도
add : O(1)
contains : O(1)
next : O(1)
# 속도는 hashSet에 비해 느리지만 좋은 성능을 보장한다.
# 등록한 순으로 정렬을 한다.
# null을 허용한다.👉 TreeSet
시간복잡도
add : O(log n)
contains : O(log n)
next : O(long n)
# 객체기준으로 정렬을 한다. 느리다.
# null을 허용하지 않는다.👉 HashMap
시간복잡도
get : O(1)
containsKey : O(1)
next : O(h/n) h는 테이블 용량
# 순서에 상관없이 저장됨, Null을 허용한다.👉 LinkedHashMap
시간복잡도
get : O(1)
containsKey : O(1)
next : O(1)
# 순서대로 등록한다. Null을 허용한다. thread-safe 보장하지 않는다.👉 ConcurrentLinkedQueue
시간복잡도
offer : O(1)
peek : O(1)
poll : O(1)
size : O(n)
# FIFO 방식 Queue
# 데이터/추가/삭제가 빠름
# size는 O(1)이 아니다.
# null을 허용하지 않는다.
컴퓨터가 할일은 컴퓨터가