시간 복잡도 (Time Complexity)

알고리즘마다 시간 복잡도를 측정하는 이유는 성능 때문이다.

데이터의 수가 늘어남에 따라서 알고리즘의 처리수가 어떻게 증가하는지를 알면

같은 문제를 해결할 때 어떤 알고리즘이 대량의 데이터를 다루기 적절한지를 파악할 수 있다.

 

컴퓨터의 연산 속도는 엄청 빨라서 작은 처리수의 증가는 의미 없고

처리수를 구하는 식에 가장 큰 영향을 주는 부분만 떼서 보는 식으로

시간 복잡도를 계산한다.

 

시간 복잡도는 Big O를 써서 다음과 같이 표현한다.
O(1), O(log n), O(n), O(n²), O(c의 n제곱)

 

O(1)은 데이터량과 관계없이 동일한 처리수를 가질 때를 말한다.

O(log n)은 데이터량이 늘어날 때 처리수가 증가하지만 갈수록 늘어나는 폭이 줄어드는 때를 말한다.

O(n)는 데이터량이 늘어나는만큼 처리수가 비례해서 늘어날 때를 말한다.

O(n²)은 데이터 수의 제곱만큼 처리수가 늘어나는 때를 말한다. 예를 들어 이중 for문을 들 수 있다.

O(c의 n제곱)는 데이터량에 따라 처리수가 기하급수적으로 커질 때를 말한다.

 

배열

 

(자바의 경우)

 

Look up 특정 인덱스의 데이터 조회 : O(1)

Assign 특정 인덱스에 데이터 바꿔 넣기 : O(1)

Insert 특정 인덱스에 데이터 끼워 넣기 : O(n)

데이터를 중간 인덱스에 넣으려면 뒤에 있는 데이터 수만큼 데이터들을 한 칸씩 뒤로 밀어줘야 한다.

Remove 특정 인덱스를 삭제하기 : O(n)

중간에 있는 데이터를 삭제하면 빈자리를 채워넣기 위해 뒤에 있는 데이터 수만큼 데이터들을 한 칸씩 앞으로 당겨줘야 한다.

Find 저장된 값을 찾기 : O(n)

데이터의 수만큼 반복해서 값을 확인해야 한다.

 

리스트

 

Look up 특정 인덱스의 데이터 조회 : O(n)

데이터의 수만큼 링크를 하나하나 따라가야 한다.

Assign 특정 인덱스에 데이터 바꿔 넣기 : O(n)

데이터의 수만큼 링크를 하나하나 따라가야 한다.

Find 저장된 값을 찾기 : O(n)

데이터의 수만큼 링크를 하나하나 따라가야 한다.

Insert 특정 인덱스에 데이터 끼워 넣기 : O(1)

특정 인덱스를 이미 알고 있다면 링크로 연결해주기만 하면 된다.

Remove 특정 인덱스를 삭제하기 : O(n)

다음 인덱스는 알지만 이전 인덱스는 알 수 없기 때문에

이전 인덱스에서 다음 인덱스를 연결해주려면

처음으로 돌아가서 이전 인덱스를 찾아야 한다.

Doubly Linked List는 O(1)이다.