Algorithm

[Algorithm] 알고리즘 선택의 기준, 시간복잡도 (Big-O 표기법)

ㅇ 알고리즘이란? 컴퓨터가 특정 문제를 해결하는 방식이다. 물론 특정 문제를 해결하는 방식이 많이 있지만, 그중에서도 효율적인 방식을 찾는 것이 중요하다. 이러한 효율적인 알고리즘을 찾는 기준은 시간복잡도이다. ㅇ 시간복잡도란? 알고리즘의 시간 복잡도는 성능을 나타내는 척도 중 하나로 알고리즘의 수행 시간을 나타낸다. 즉, 프로그램이 얼마나 많은 시간이 걸리는지를 나타내는 것이다. 다시 말하면, 시간복잡도는 주어진 문제를 해결하기 위한 연산 횟수를 말한다. 일반적으로 수행시간은 1억번의 연산을 1초의 시간으로 간주한다. 시간복잡도가 큰 알고리즘은 작은 데이터에서도 느리게 동작하는 반면, 시간복잡도가 작은 알고리즘은 빠르게 동작한다. ㅇ 시간복잡도 유형 이러한 시간복잡도를 정의하는 3가지 유형이 있다. ①..