알고리즘의 효율성을 나타내는 함수, Big-O
현대에 이르러 컴퓨터가 방대한 크기의 데이터를 처리해야 하는 일이 생겨나면서 이를 다뤄 유의미한 결과를 도출해내는 알고리즘 또한 데이터를 빠르게 처리할 수 있도록 요구되어 왔습니다. 버블, 선택, 삽입, 퀵 정렬은 모두 '정렬한다'는 기능적인 면은 같지만 과정 중 소요되는 시간은 매우 다릅니다. 같은 데이터를 주어도 버블 정렬은 1초 걸리는 일을 퀵 정렬은 0.01초만에 해낼 수 있습니다. 이렇게 알고리즘이 어떠한 과정을 수행하는데에 얼마나 많은 시간이 걸리느냐를 말하는 것이 시간복잡도(Time Complexity)이고 이는 곧 알고리즘의 효율성을 나타냅니다. 빅-O 표기법은 시간복잡도를 나타내는 일반적인 방법입니다.
입력 데이터에 따라 표기
모든 알고리즘은 입력 데이터에 따라 수행되도록 작성되어 있습니다. 따라서 이 입력 데이터의 수가 얼마나 방대한가에 따라 알고리즘이 실행되는 시간도 달라집니다. 빅-O 표기법은 이러한 논점을 잡아 데이터의 수(상수)를 나타내는 N에 대한 함수로 표현됩니다. 이때 앞에 나오는 상수는 시간복잡도를 비교할 때 큰 의미가 있는 것이 아니므로 생략합니다. 이 두 가지를 통해 예시를 빅-O 표기법으로 바꿔보겠습니다.
만약 처리 시간이 각각 100N초, 0.2N^2초인 A, B알고리즘이 있을 때 N이 10이라면 1000초, 20초가 걸릴 것입니다. 100이라면 10000초 2000초. 10000이라면 1000000초, 20000000초, B가 A보다 20배 더 느리게 작동합니다. 이는 데이터가 많아지면 많아질 수록 B가 더 느리다는 것을 알 수 있게 해줍니다. 이때 앞에 붙은 상수보다도 N이 제곱인가, 아닌가에 따라 비교가 달라지므로 상대적으로 중요성이 떨어짐을 알 수 있습니다. 따라서 빅-O 표기법에서는 큰 의미가 없는 이상 상수는 표기하지 않습니다.
- 위 예시에 따른 알고리즘별 빅-O 표기법
- A 알고리즘 : O(N)
- B 알고리즘 : O(N^2)
+ 가장 이상적인 상수 빅-O
이제까지 빅-O에 대해 알아봤습니다. 입력 데이터의 개수가 함수에서 어떤 지위를 갖느냐가 중요함이 보이시죠. 이는 데이터의 입력을 다루는 것에겐 어쩔 수 없는 당연한 이치입니다. 그러나 이러한 이치를 깰 수만 있다면 가장 이상적인 빅-O를 가진 알고리즘을 만들 수 있을 것입니다. 바로 O(1)과 같은 상수 빅-O의 알고리즘을요. 어떤 무지막지한 데이터가 들어와도 1년만에 처리할 수 있는 알고리즘이 있다면 인간의 모든 생각을 담은 사전이 출판될 수도 있습니다. 물론 2개의 데이터를 정렬하는 데에도 1년이 걸립니다. 하지만 데이터의 개수에 제약이 없는 알고리즘은 시간복잡도가 얼마나 크던 대단한 혁명이 될 것입니다. 수학적 원리에 따라 불가능한 것이긴 합니다만 이상적인 무엇인가가 있다는 건 그만큼 가까워지고자하는 목표가 존재한다는 것이니 알고리즘의 발전이 계속되어 이상에 가까워졌으면 좋겠습니다.