1.
알고리즘 복잡도
•
하나의 문제를 푸는 알고리즘은 다양할 수 있음
◦
정수의 절대값 구하기
◦
1,-1 → 1
◦
방법1 : 정수값을 제곱한 값에 다시 루트를 씌우기
◦
방법2: 정수가 음수인지 확인해서, 음수일 때만, -1 을 곱하기
◦
다양한 알고리즘 중 어느 알고리즘이 더 좋은지를 분석하기 위해, 복잡도를 정의하고 계산함
2.
알고리즘 복잡도 계산 항목
a.
시간 복잡도 : 알고리즘 실행 속도
b.
공간 복잡도 : 알고맂므이 사용하는 메모리 사이즈
- 가장 중요한 시간 복잡도를 꼭 이해라고 계산할 수 있어야함.
3.
알고리즘 시간 복잡도의 주요 요소
- 반복문이 지배
자동차로 서울에서 부산을 가기 위해, 다음과 같이 항목을 나누었을 때, 가장 총 시간에 영향을 많이 미칠 것 같은 요소는?
•
자동차로 서울에서 부산가기
1.
자동차 문열기
2.
자동차 문닫기
3.
자동차 운전석 등받이 조정하기
4.
자동차 시동걸기
5.
자동차로 서울에서 부산가기
6.
자동차 시동끄기
7.
자동차 문열기
8.
자동차 문닫기
•
마찬가지로, 프로그래밍에서 시간 복잡도에 가장 영향을 많이 미치는 요소는 반복문
◦
입력의 크기가 커지면 커질수록 반목문이 알고리즘 수행 시간을 지배함
알고리즘 성능 표기법
•
Big O(빅-오) 표기법 : O(N)
◦
알고리즘 최악의 실행 시간을 표기
◦
가장 많이/일반적으로 사용
◦
아무리 최악의 상황이라도, 이정도의 성능은 보장한다는 의미이기 때문
•
Ω(오메가) 표기법 : Ω(N)
◦
오메가 표기법은 알고리즘 최상의 실행 시간을 표기
•
Θ(세타) 표기법 : Θ(N)
◦
세타 표기법은 알고리즘 평균 실행 시간을 표시
시간 복잡도 계산은 반복문이 핵심 요소임을 인지하고, 계산 표기는 최상, 평균, 최악 중, 최악의 시간인 Big-O 표기법을 중심으로 익히면됨
3.
대문자 O 표기법
•
빅 오 표기법, Big-O 표기법이라고도 부름
•
O(입력)
◦
입력 n에 따라 결정되는 시간 복잡도 함수
◦
O(1), O(), O(n), O(),O(),O(n!)등으로 표기함
◦
입력 n의 크기에 따라 기하급수적으로 시간 복잡도가 늘어날 수 있음
◦
O(1)<O()<O(n)<O()<O()<O()<O(n!)
▪
참고 : 의 베이스는 2-log2(밑)n
◦
단순하게 입력 n에 따라, 몇번 실행이 되는지를 계산하면 됩니다.
◦
표현식에 가장 큰 영향을 미치는 n의 단위로 표기합니다.
▪
n이 1이든 1000이든 10000이든 실행을 무조건 2회 실행한다 : O(1)
ex)
if(n > 10)
{
System.out.println(n);
}
Java
복사
•
n에 따라, n번, n+10번, 또는 3n+10번 등을 실행한다 : O(n)
◦
다음 코드는 이중 반복문이지만, 상위는 상수로 반복하므로 3n 실행
for(int num = 0; num < 3; num++){
for(int index = 0; index < n; index ++){
System.out.println(index);
}
}
Java
복사
•
n에 따라 번 +1000번, 100-100 번 등 실행한다 : O()
◦
다음 코드는 삼중 반복문이지만, 상위는 상수로 반복하므로, 3 실행
for(int i=0;i<3;i++){
for(int num=0;num<n;num++){
for(int index=0;index<n;index++){
System.out.println(index);
}
}
}
Java
복사
•
빅 오 입력 값 표기 방법
◦
예 :
▪
만약 시간 복잡도 함수가 2+3n 이라면
•
가장 높은 지수 2
•
상수는 실제 큰 영향이 없음
•
결국 빅 오 표기법으로는 O()
4.
실제 알고리즘을 예로 각 알고리즘의 시간 복잡도와 빅 오 표기법 알아보기
•
1 부터 n 까지의 합을 구하는 알고리즘
4.1 알고리즘1 : 1부터 n까지의 합을 구하는 알고리즘 1
•
합을 기록할 변수를 만들고
•
n을 1부터 1씩 증가하면서 반복
•
반복문 안에서 합을 기록할 변수에 1씩 증가된 값을 더함
•
반복문이 끝나면 합을 출력
pulbic class main{
public int sum(int n){
int total = 0;
for(int i=1;i<n+1;i++){
total += i;
}
return total;
}
}
Java
복사
•
시간 복잡도 구하기
◦
입력 n에 따라 덧셈을 n번 해야 함(반복문)
◦
시간 복잡도 : n, 빅오 표기법으로 O(n)
4.2 알고리즘2 : 1부터 n까지의 합 2
•
n(n+1)/2
public class Main {
public int sum(int n) {
return n * (n + 1) / 2;
}
}
Java
복사
•
시간 복잡도 구하기
◦
입력 n이 어떻든 간에, 곱셈/덧셈/나눗셈 하면 됨(반복문 없음)
◦
시간 복잡도 : 1, 빅오 표기법으로는 O(1)
•
4.3 어느 알고리즘이 성능이 좋은가요?
◦
알고리즘2