알고리즘
어떤 문제를 풀기 위한 절차나 방법
주어진 입력을 출력으로 만드는 과정을 구체적으로 명료하게 표현한 것
1부터 n까지의 합을 구하는 알고리즘
- 방법 1
값을 1씩 증가시키면서 덧셈 연산
- 방법 2
가우스 등차수열의 합 공식 활용
$$ S_n = \frac{n*(n+1)}{2} $$
알고리즘 분석
주어진 문제를 푸는 여러 가지 방법 중 어떤 방법이 더 좋은지 판단할 때 필요하며, 분석에는 복잡한 수학 이론이 필요한 경우가 많다.
입력 크기가 알고리즘의 수행 성능에 영향을 미치는 경우가 많으므로, 입력 크기가 매우 큰 경우에 대해 따져보는 것이 중요하다.
계산 복잡도(Complexity)
O() 표기법(Big O)을 가장 많이 사용한다. 알고리즘의 대략적인 성능을 표시하며 필요한 계산 횟수와 입력 크기와의 관계를 표현한다.
- O(n)
필요한 계산 횟수가 입력 크기에 정비례하다. 입력 크기와 계산 시간이 대체로 비례한다. - O(1)
필요한 계산 횟수가 입력 크기와 무관하다. 입력 크기가 커져도 계산 시간이 늘어나지 않는다.
시간 복잡도(time complexity)
어떤 알고리즘을 수행하는 데 얼마나 오랜 시간이 걸리는지 분석
공간 복잡도(space complexity)
어떤 알고리즘을 수행하는 데 얼마나 많은 공간(메모리/기억 장소)이 필요한지 분석
참고문서
728x90