알고리즘이란?
알고리즘은 문제를 해결하기 위한 일련의 과정을 의미한다. 알고리즘은 각기 다른 모양과 형태를 지니고 있기 때문에 시간 복잡도를 설명하는데 자주 사용된다. 시간복잡도를 분석하는 것은 입력값 n에 대하여 알고리즘이 문제를 해결하는 데에 얼마나 오랜 시간이 걸리는 지를 분석하는 것과 같다. 그리고 이는 Big-O 표기를 이용하여 정의할 수 있다.
Big-O 표기란?
Big-O notation is a way of converting the overall steps of an algorithm into algebraic terms, then excluding lower order constants and coefficients that don’t have that big an impact on the overall complexity of the problem.
Big-O표기법은 알고리즘의 전체 단계를 대수 용어로 변환한 다음, 문제의 전체 복잡성에 큰 영향을 미치지 않는 하위 순서 상수와 계수를 제외하는 방법이다.
시간복잡도에서 중요한 것은 정해진 표현식에 가장 큰 영향을 미치는 n의 단위이다.
O(1) - 상수 시간
입력값 n이 주어졌을 때, 알고리즘이 문제를 해결하는데 오직 한 단계만 거친다. 즉 값을 검색할 때, 객체에서 키를 알거나 배열에서 인덱스를 알고 있으면 언제나 한 단계만 걸린다.
O(log n) – 로그 시간
입력값 n이 주어졌을 때, 문제를 해결하는데 필요한 단계들이 연산마다 특정 요인에 의해 줄어든다. 즉 배열에서 값을 찾을 때, 어느 쪽에서 시작할 지를 알고 있으면 검색하는 시간이 두 배로 줄어든다. 예를 들어 tree형태를 말한다.
O(n) – 직선적 시간
문제를 해결하기 위한 단계의 수와 입력값 n이 1:1 관계를 가진다.
O(n^2) – 2차 시간
문제를 해결하기 위한 단계의 수는 입력값 n의 제곱이다.
O(C^n) – 지수 시간
문제를 해결하기 위한 단계의 수는 주어진 상수값 C 의 n 제곱이다. 지수시간은 보통 문제를 풀기 위해 모든 조합과 방법을 시도할 때 사용된다.
