[자료구조] 시간 복잡도와 공간 복잡도

 시간 복잡도

시간 복잡도는 연산하는 기기마다 성능이 다르므로, 시간 소요가 아니라 연산 횟수를 기준으로 계산합니다.

시간복잡도의 유형에는 세가지가 있습니다.

1. 빅 오메가 Ω : 주어진 알고리즘보다 시간복잡도가 느릴때

2. 빅 세타 θ : 빅오메가와 빅 오가 같을때

3. 빅 오 O : 주어진 알고리즘보다 시간복잡도가 같거나 더 클때

N = int(input())
M = int(input())

s = 0
for i in range(N):
    for j in range(M):
        if i + j != 10:
            s = s + i


print(s)

위의 예문에서, 시간복잡도를 구해보겠습니다.

1.  빅 오메가 :  O(1) , O(N) => 주어진 알고리즘보다 시간 복잡도가 느릴때

2.  빅 세타 : θ(N) =>  빅 오메가와 빅 오가 같을때

3.  빅 오 :   O(N), O(N^2) => 주어진 알고리즘보다 시간복잡도가 같거나 더 느릴때

 

공간 복잡도

공간 복잡도는 특정한 크기의 입력에 대하여 알고리즘이 얼마나 많은 메모리를 차지하는지 구하는 것입니다.

 

시간복잡도와 공간복잡도의 관계는 trade off 입니다.

기록(공간)이 많으면 시간이 줄어듭니다. 

기록(공간)이 적으면 시간이 줄어듭니다.

 

메모를 생각해보면 이해하기 쉽습니다. 참고할 메모가 많으면 거기서 원하는 값을 쉽게 얻을 수 있습니다. 하지만 메모가 적다면 메모장 이외의 다른 것들에서 원하는 값을 찾아야 하기 때문에 시간이 많이 소요됩니다.

 

배열, 리스트, 스택, 큐의 시간복잡도와 공간복잡도

배열

배열의 핵심은! 특정, 임의의 인덱스를 읽어오는 기능, 특정 인덱스의 값을 수정하는 기능을 가진다는 것입니다.

그 외의 특징으로 네가지가 있습니다.

1. 크기를 바꿀 수 없으며(고정된 크기) 연속된 데이터를 가집니다.

2. 인덱스를 가집니다.

3. 같은 자료형의 데이터들을 하나의 변수로 정의합니다.

4. 메모리 주소가 순차적입니다.

 

* 삽입 삭제 안됨, 비어있는 배열의 값이 존재하지 않음

배열의 시간 복잡도

1. 특정, 임의의 인덱스의 값을 읽어오는 기능

n번째 인덱스에서 해당하는 값을 찾아내는 연산이기 때문에  O(1)오더1의 시간 복잡도를 가집니다.

 

2. 특정 인덱스의 값을 수정하는 기능

자료마다 인덱스가 있어서 수정하고자 할때, 해당 인덱스로 가서 수정할 수 있기 때문에 O(1)의 시간 복잡도를 가집니다.

 

3. 배열 선언 O(n)

연결 리스트

• 값을 삽입, 삭제 하기 위해서 사용하는 자료 구조입니다.
• 인덱스가 없으며 본래 정해져 있는 크기가 없습니다.

리스트의 기능

어떤 위치에 있는지만 알면된다. 다음 호칸으로 이동할 것인지 내가 있는칸의 값을 읽어올 것인지 내가 있는 칸 다음에 새로운 값을 넣을 것인가? 

• 다음 위치로 이동하는 기능이 있습니다.
• 현재 위치의 값을 읽어 올 수 있는 기능이 있습니다.
• 현재 위치의 값을 삭제 할 수 있는 기능이 있습니다.
• 현재 위치의 값을 추가하는 기능이 있습니다.
• 맨 처음으로 이동하는 기능

리스트의 시간 복잡도 O(1)

스택

top : 가장 위에 있는 데이터

LIFO(Last-In, First Out) : 마지막에 삽입한 데이터를 가장 먼저 사용합니다.

 

구성 요소

<필수>

PUSH : item 넣기

POP : item 제거

<필수 x>

PEEK

• 가장 위에 있는 데이터를 보는 기능입니다.
•  POP 을 입력한 후 PHSH 를 입력하면  PEEK 이 됩니다.

시간 복잡도

PUSH, POP :  O(1)

삭제나 삽입 시 맨 위에 데이터를 삽입하고 삭제하기 때문입니다.

* 공간복잡도는  O(n)입니다. ( 데이터 갯수만큼 공간을 차지 하기 때문입니다.)

 

큐               

tail(rear) : 맨 뒤에 있는 데이터를 가리키는 포인터입니다.

FIFO : 가장 먼저 줄 선 사람이 먼저 서비스를 받는 형식입니다.

 

구성요소

<필수> 

ENQUEUE = PUSH : item 을 넣기

DEQUEUE = POP : item을 제거하기

<필수 x>

PEEK : POP, PUSH 연산을 n번하면 됩니다.

시간 복잡도

• enqueue : O(1) : 맨 뒤에 있는 자료가 삽입되는 연산만을 수행하기 때문입니다.
• dequeue : O(1) : 맨 앞에 있는 자료에 연산만 수행하기 때문입니다.

O(n)으로 구현할 수도 있음

 

* 공간복잡도 (메모리 사용) -> O(n)