알고리즘(이충기 교수)
알고리즘 2주차( 알고리즘의 효율성 분석)
유민기
2023. 9. 25. 16:21
시간 복잡도란?
- 알고리즘이 얼마나 빨리 수행되는지를 나타내는 것
공간 복잡도란?
- 알고리즘이 수행되는 동안 요구되는 메모리 공간의 크기
알고리즘은 3가지로 분석할 수 있다
- 입력크기, 실행 시간 측정 단위, 증가 차수
입력 크기
- 배열의 크기
- 연결 목록의 길이
- 행렬에서 행과 열의 크기
- 그래프에서 정점과 간선의 수
덕수궁에서 창덕궁을 가는데 가장 빠른 길은 어떻게 찾아야 할까?
일단 갈 수 있는 루트들을 모두 조사해보자
덕수궁 - 경희궁 - 경복궁 - 창덕궁
덕수궁 - 경복궁 - 창덕궁
덕수궁 - 종묘 - 창덕궁
덕수궁 - 경희궁 - 경복궁 루트는 1 + 0.7 = 1.7로 덕수궁 -경복궁 = 1.3보다 크기때문에 제외한다.
덕수궁 - 경복궁 - 창덕궁 = 3.4 > 덕수궁 - 종묘 - 창거궁 = 3.5
따라서 덕수궁 - 경복궁- 창덕궁 = 3.4가 가장 ㅈ빠른 루트임을 알 수 있다.
위 코드의 알고리즘은
입력크기 : n
기본연산 : sum += i*j
시간 복잡도 : n*(n + 1)/2 -> n^2
증가 차수란
시간 복잡도 함수의 입력 크기(N)에 따른 증가율을 의미한다.
실행 시간은 입력 크기가 작으면 거의 차이가 없다.
–로그 함수(〖log〗_2 𝑁): N의 값이 4배 증가할 때 2만큼 증가
–1차 선형 함수(N): N의 값에 비례하여 증가
–2차 선형 함수(N^2): N의 값이 4배 증가할 때 16배 증가
–지수 함수(2^N): N의 값이 4배 증가할 때 2의 4 제곱배 증가
시간 복잡도의 분류 - 최악, 평균, 최선의 경우
최악 경우(worst-case) 시간 복잡도
–모든 입력에 대해서 기본 연산이 수행되는 최대 횟수
최선 경우(best-case) 시간 복잡도
–모든 입력에 대해서 기본 연산이 수행되는 최소 횟수
평균 경우(average-case) 시간 복잡도
–모든 입력에 대해서 기본 연산이 수행되는 평균 횟수
–일반적으로 최악 경우보다 구하기가 어려움
빅 O 표기법
O(1) - 상수 시간
O(log n) - 로그(대수) 시간
O(n) - 선형 시간
O(n log n) - 로그 선형 시간
O(n2) - 제곱 시간
O(n3) - 세제곱 시간
O(2n) - 지수 시간
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int square = 0;
// square = n * n;
//for(int i=0; i < n; i++){
// square += square;
//}
for(int i=0; i < n; i++){
for(int j=0; j < n; j++){
square += 1;
}
}
System.out.print(square);
}
위 알고리즘을 개선해보자. CUME[]를 계산하는 과정에서 중복계산이 되고있다 이를 제거하고 효율적으로 돌아가도록 빠른 알고리즘을 만들어 보자.
