[프로그래밍] 빅 O의 아규먼트가 크다고 꼭 느린 건 아니다 – O(n)

컴퓨터 프로그래밍을 하다 보면 컬렉션을 다룰 때 O(1)이나 O(n)이라는 표기를 흔히 접하게 된다. 이를 흔히 Big O라 하며 Big-O, Big O Notation, 빅 오 표기법, 점근표기법 등으로 부르기도 한다. big은 o를 대문자로 표기한다는 뜻이고 o는 순서라는 뜻의 독일어 Ordnung을 뜻한다. 독일 사람들은 명사의 첫 글자를 대문자로 표기한다.

쉽게 설명하면 괄호 안의 수는 작을수록 좋다. 이 수가 클수록 앨거리듬이 복잡하게 작동하여 결과가 늦게 나온다. 하지만 크다고 꼭 나쁜 건 아니다. 예를 들면 아래의 경우다.

.네트의 list에 100개의 아이템들이 있다. RemoveRange로 앞의 90개를 지우면 이는 O(10)이다. 남은 10개를 앞으로 옮겨야 하는데 이 작업이 논리적으로는 열 번을 해야 하는 거기 때문이다. 그러나 실제로는 다르다. 남은 엘리먼트들을 하나씩 열 번에 옮기지 않고 한꺼번에 block copy를 한다. 논리적으로는 O(10)이지만 사실적으로는 O(1)이다. 여기에서 사실적이라는 말은 앨거리듬의 차원에서 그렇다는 게 아니라 그 뒤의 실행 단계에서 앨거리듬을 초월한 변칙을 쓰는 상황을 뜻한다. 따라서 논리를 의미하는 O를 위 경우에 쓰는 건 이해를 돕기 위한 거지 굳이 따지자면 맞지 않다.