연산횟수가 늘어난다고 해서 복잡도라는 표현을 쓰는 것이 맞을까?

이건 외국인 즉 시간복잡도, Time Complexity를 이름 붙인 서양인의 관점에서 생각해보아야 한다.

복잡하다는 감정적인 단어보다 왜 복잡이라는 단어가 나왔는지 이유에 대해 봐야한다. 해당 설명에서는 "여러 부분"이라는 단어가 나왔다. 이 키워드에 집중을 해보자

여러 부분이라는게 뭘 의미하는 걸까?

단순한 순차탐색인 O(n)이라면 하나의 배열에서 모든게 이루어진다. 그러면 하나의 부분일까? 아니다. 해당 배열에서도 연산구조가 여러개로 나뉜다. 바로 루프와 조회 등등이다.

이러한 관점에서 보면 모든 알고리즘은 여러 연산 구조로 이루어져있기 때문에 "복잡도"라는 단어를 쓰는 것이 타당한 것이다.

하지만 왜 하필 "시간"일까.

왜 하필 시간일까?

여러 연산이 걸리는 횟수를 표현한 것이기 때문에 횟수 복잡도가 맞지 않을까? 시간이 먼저는 아니지 않는가. 연산횟수가 적어지면 연산 시간이 줄어들거 아닌가.

과연 그럴까? 연산횟수가 무조건 적은 연산이 연산 시간이 적다고 말할 수 있냐는 말이다. "시간"이라는 단어가 붙은 이유는 이러한 현실적인 예외 속에 있다.

CPU는 항상 같은 연산 횟수를 처리할 때, 동일 연산 시간이 보장되어 지지 않는다. 다양한 변수들이 존재하기 때문이다. 메모리, 유동적인 클럭 등 다양한 이유들이 그 예시이다. 따라서 인간의 관점에서 인간의 문제를 해결할 수 있는데, 사용할 수 있는 인간이 정해놓은 지표인 "시간"을 사용하는 것이다.

그래서 시간 복잡도가 뭔데

결론은 시간복잡도는 여러부분으로 이루어진 인간이 측정할 수 있는 시간이라는 단위를 사용하여 포장한 "연산 횟수"를 의미한다.

복잡도라는 단어를 쓰는 이유는 여러 연산 로직이 들어가 있어서 이고 시간이라는 단어를 쓰는 이유는 CPU 동일 연산 시간별 동일 연산 횟수를 보장하지 않기 때문에, 인간 입장에서 절대적으로 측정할 수 있는 지표인 시간을 사용한 것이다. (해당 지표를 써서 컴퓨팅 자원 소모를 아낌으로서 비용 및 시간적인 측면에서 아낄 수 있고 이는 회사의 성장으로 이어진다)