[HUFS/알고리즘] #1 알고리즘과 시간 복잡도

알고리즘이란?

 알고리즘(Algorithm) = 문제를 해결하기 위한 단계적인 절차

* 해결 방법은 다양하지만 가장 효율적인 방법을 찾는 것에 의의가 있다

 

알고리즘의 특성

• 정확성: 주어진 입력에 대해 올바른 해를 주어야 한다
• 수행성: 각 단계는 컴퓨터에서 수행 가능해야 한다
• 유한성: 일정한 시간 내에 종료되어야 한다
• 효율성: 효율적일수록 그 가치가 높아진다

 

유클리드(Euclid)의 최대공약수 알고리즘 = 최초의 알고리즘

 

2개의 자연수의 최대공약수는 큰 수에서 작은 수를 나눈 나머지와 작은 수의 최대공약수와 같다

 

알고리즘의 표현 방법

알고리즘은 프로그래밍 언어나 의사 코드(pseudo code)로 표현할 수 있다

 

최대값 알고리즘을 표현하는 다양한 방식..

 

1. 보통 말로 표현

2. 의사 코드로 표현

3. 플로우 차트(flow chart)로 표현

 

알고리즘의 분류

문제 해결 방식에 따른 분류

• 분할 정복(Divide-and-Conquer) 알고리즘
• 그리디(Greedy) 알고리즘
• 동적 계획(Dynamic Programming) 알고리즘
• 근사(Approximation) 알고리즘
• 백트래킹(Backtracking) 기법
• 분기 한정(Branch-and-Bound) 기법

 

문제에 기반한 분류

• 정렬 알고리즘
• 그래프 알고리즘
• 기하 알고리즘

 

특정 환경에 따른 분류

• 병렬 (Parallel) 알고리즘
• 분산 (Distributed) 알고리즘
• 양자 (Quantum) 알고리즘

 

알고리즘의 효율성

알고리즘의 효율성은 다음 두 가지로 판단한다

• 시간복잡도(time complexity): 알고리즘의 수행 시간
• 공간복잡도(space complexity): 사용되는 메모리 공간의 크기

* 일반적으로 성능 측정에는 시간 복잡도가 사용

 

시간 복잡도 측정 기준은 기본 연산(Elementary Operation)의 횟수이다

ex) 데이터의 비교, 읽기와 갱신,  연산 등..

 

시간복잡도 표현 방법

• 최악경우 분석(Worst-case Analysis): 수행시간의 상한(Upper Bound)을 의미
• 평균경우 분석(Average-case Analysis): 수행시간의 일반적 균등분포(Uniform Distribution)를 가정
• 최선경우 분석(Best-case Analysis): 가장 빠른 수행시간의 최적(Optimal) 알고리즘 분석
• 상각 분석(Amortized Analysis): 수행시간을 모두 더하고 총 연산 횟수로 나누어 분석

* 일반적으로 알고리즘의 수행시간은 최악경우 분석으로 표현

 

점근적 표기(Asymptotic Notation): n이 무한대로 커질 때의 복잡도를 표기하는 방법

다항식 함수로 표현된 시간복잡도의 점근적 상한을 표기한 것이 빅오 표기법(big-O notation)이다

 

O(n^2) ~ n이 무한대로 증가할 때의 점근적 상한

자주 사용하는 O-표기

빅오 표기법은 시간단위가 아닌 단계 수만을 고려한다

• 배열의 끝에 삽입이나 삭제: O(1)
• 배열의 선형검색: O(n)
• 배열의 이진검색: O(logn)

 

데이터 증가에 따른 연산(단계) 수의 변화

* 10억개의 숫자를 정렬할 때, O(n^2)알고리즘은 300여년, O(nlogn)알고리즘은 5분이 걸린다