[Algorithm] 시간 복잡도와 공간복잡도

[hwangJi-dev]

🧸 제한사항

• 시간 제한 1초
  • 프로그램이 시작하고, 결과를 1초 안에 내고 정상적으로 종료되어야 한다는 의미
• 메모리 제한 256MB
  • 이 프로그램이 메모리를 256MB 이하로 사용해야 한다.

시간복잡도

입력의 크기와 문제를 해결하는데 걸리는 시간의 상관관계

컴퓨터가 1초에 할 수 있는 연산의 단위: 어림잡아 3-5억

1 + 1 + n x (2 + 2 + 1) + 1 = 5n + 3

⇒ n에 비례한다.

문제

대회장에 N명의 사람들이 일렬로 서있다. 거기서 당신은 이름이 ‘가나다’인 사람을 찾기 위해 사람들에게 이름을 물어볼 것이다. 이름을 물어보고 대답을 듣는데까지 1초가 걸린다면 얼마만큼의 시간이 필요할까?

정답

앞에서부터 차례대로 물어보면 된다.

최악의 경우 N초, 최선의 경우 1초, 평균적으로 N/2초가 필요하므로

결과적으로 걸리는 시간은 N에 비례한다.

문제

대회장에 N명의 사람들이 일렬로 서있다. 거기서 당신은 이름이 ‘가나다’인 사람을 찾기 위해 사람들에게 이름을 물어볼 것이다. 이 때 사람들은 이름 순으로 서있다. 이름을 물어보고 대답을 듣는데까지 1초가 걸린다면 얼마만큼의 시간이 필요할까?

정답

업다운게임을 하듯이 중간 사람에게 계속 물어보면 된다. 최선의 경우 1초, 최악의 경우 logN초, 평균적으로 logN초가 필요하다.

결과적으로 걸리는 시간은 logN에 비례한다.

빅오표기법

주어진 식을 값이 가장 큰 대표항만 남겨서 나타내는 방법

O(N): 5N + 3, 2N + 10logN, 10N : 선형 시간

O(logN): 로그 시간

O(N^2): N^2 + 2N + 4, 6N^2 + 20N + 10logN : 다항 시간

O(NlogN): NlogN + 30N + 10, 5logN + 6 : 다항 시간

O(1): 5, 16, 36 // 값이 상수일 떄

O(1) < O(logN) < O(N) < O(NlogN) < O(N^2) < O(2^N) < O(N!)

O(1) : 상수시간

O(logN) : 로그 시간

O(N) : 선형 시간

O(NlogN) : 다항 시간

O(N^2) : 다항 시간

O(2^N) : 지수 시간 → N이 25 이하 정도로 작은 수가 아니라면 시간 제한을 통과하기 힘들어짐.

O(N!) : 지수 시간보다 더 가파르게 올라감 → N이 11이하 정도로 굉장히 작은 수가 아니라면 시간 제한을 통과하기 힘듦.

💡 예를 들어, 주어진 배열을 크기 순으로 정렬하는 문제를 생각해보자

• O(NlogN)으로도 해결할 수 있고 O(N^2)로도 해결할 수 있다.
  • N이 1000이하라면 둘 중 어느 것을 쓰더라도 눈 깜빡할 사이에 정렬이 완료되지만
  • N이 100만이라면 O(NlogN)은 1초 내로 정렬이 완료되는데 반해, O(N^2)는 정렬되는데 1시간 가까이가 소요될 것이다.

• 주어진 문제를 보고 풀이를 떠올린 후에 무턱대고 바로 그걸 짜는게 아니라, 내 풀이가 이 문제를 제한시간 내로 통과할 수 있는지, 내 알고리즘의 시간복잡도가 올바른지를 꼭 생각하자.
• 그렇다면 내 풀이의 시간복잡도를 어떻게 알 수 있느냐?
  • 1부터 N까지의 수를 다 돌아야 하면 → O(N)
  • 이중 for문이라면 → O(N^2)

공간복잡도

입력의 크기와 문제를 해결하는데 필요한 공간의 상관관계

512MB = 1.2억개의 int