Untitled

컴퓨터 과학자는 서로 간에 시간 복잡도를 쉽게 소통할 목적으로 자료 구조와 알고리즘의 효율성을 간결하고 일관된 언어로 설명하기 위해 수학적 개념을 차용했다.

이러한 개념을 형식화한 표현을 빅 오 표기법이라고 부른다. 빅 오 표기법을 사용해 주어진 알고리즘의 효율성을 쉽게 분류하고 이해시킬 수 있다.

3-1 빅 오 : 원소가 N개일 때 몇 단계가 필요할까?

빅 오는 특정 방식으로 알고리즘에 필요한 단계 수를 고려함으로써 일관성을 유지한다. 최악의 경우 선형 검색에는 배열의 원소 수만큼의 단계가 필요하다. 빅 오 표기법으로는 O(N)이라 표기한다.

O(N)은 데이터 원소가 N개일 때 알고리즘에 N단계가 필요하다.

배열에 원소가 N개일 때 선형 검색에 몇 단계가 필요할까? 선형 검색에는 N단계가 필요하므로 O(N)으로 표현한다. 그래서 O(N)인 알고리즘을 선형 시간을 갖는 알고리즘이라고도 부른다

배열 읽기에 필요한 단계 수는 배열에 크기와 상관없이 딱 하나 따라서 O(1)이라 표현하고 “오 1” 이라고 발음한다. 즉, 배열에 원소가 몇 개든 배열에서 읽기는 항상 한 단계면 된다.

이러한 이유로 O(1)을 “가장 빠른" 알고리즘 유형으로 분류한다. 데이터가 늘어나도 O(1) 알고리즘의 단계 수는 증가하지 않는다.

O(1) 알고리즘을 상수 시간을 갖는 알고리즘이라고도 표현한다.

3-2 빅 오의 본질

빅 오 표기법은 머릿속에 새겼던 핵심 질문. 즉, 데이터 원소가 N개일 때 알고리즘에 몇 단계가 필요한가에 대한 답이다.

데이터가 몇 개든 항상 3단계가 걸리는 알고리즘을 가정해보면 원소가 N개일 때 알고리즘에 항상 3단계가 필요하다 이를 빅 오로 표현하면 O(3)이 아니라 O(1)이다.

빅 오의 본질이란 빅 오가 진정으로 의미하는 것 즉, 데이터가 늘어날 때 알고리즘의 성능이 어떻게 바뀌는지를 말한다. 빅 오는 단순히 알고리즘에 필요한 단계 수만 알려주지 않는다. 데이터가 늘어날 때 단계 수가 어떻게 증가하는지 설명한다.

3-2-1 빅 오의 본질 더 파고들기

만일 데이터 크기에 상관없이 항상 100단계가 걸리는 상수 시간 알고리즘이 있다고 가정하자.

원소가 100개 이하인 데이터 세트에서는 100단계가 걸리는 O(1) 알고리즘보다 O(N) 알고리즘이 단계 수가 적다.

하지만, 100보다 큰 모든 배열에서는 O(N) 알고리즘에 다 많은 단계가 걸린다.

100보다 큰 순간부터 무한대까지 O(N)은 O(1)보다 더 많은 단계를 필요로 한다. 100단계 뿐 아니라 백만 단계여도 마찬가지이다. 데이터가 증가할 수록 O(N)이 O(1)보다 덜 효율적인 어떤 지점에 반드시 다다르게 된다.

따라서, O(N)이 전반적으로 O(1)보다 덜 효율적이다.