기초 개념
시간복잡도
1억 번이면 1초, 그래서 어쩌라고
번호표가 100,000장 있습니다. 번호가 같은 두 장이 있는지 찾습니다. 같은 번호가 없을 수도 있습니다.
컴퓨터는 1초에 약 1천만 번 일합니다. 1초 안에 끝날 방법을 모두 고르세요.
두 방법 중 0개를 맞혔습니다. 시간은 대부분 몇 번 하느냐가 정합니다.
- 시간을 정하는 것 — 컴퓨터 속도가 아니라 일하는 횟수
- 횟수를 정하는 것 — 장 수 N 과 방법
- 표시해 두기가 빠른 이유 — 번호로 칸을 바로 찾아간다. 장마다 확인이 딱 한 번이다
N 장 → 모두와 모두 N² · 한 번씩 NN 이 커질 때 횟수가 대략 이만큼 느는지 적은 것 = 시간복잡도
이 표기에는 O 를 붙여 O(N²), O(N)처럼 적습니다. O( ) 는 “N 이 커지면 횟수가 대략 이만큼 는다”는 표시입니다.
세 번째 방법도 있습니다. 번호순으로 줄을 세우면 같은 번호는 이웃이 되어 옆 장과만 견주면 됩니다. 줄 세우는 데 O(N log N) 이 들고 10만 장이면 약 1,660,964번이라 1초 안에 듭니다.
log N = N 을 절반씩 줄여 1 이 되기까지 걸리는 횟수입니다. 1,024 → 512 → … → 1 은 10번이라 log 1,024 = 10 입니다.
N 이 얼마인지가 방법을 정한다
N 을 바꿔 눌러 보세요. 어느 줄이 1초를 넘는지 보입니다.
Python 은 넉넉히 느리게 잡아 1초에 약 1천만 번으로 셉니다. 1초를 넘으면 ✘ 와 걸리는 시간이 뜹니다.
- N 이 50만 이하 — N log N 까지 버틴다
- N 이 3천 안팎 이하 — N² 까지 버틴다
- N 이 20 안팎 이하 — 2^N 도 된다. 모든 경우를 다 해 본다는 뜻이다
Python 은 C++ 보다 느려서 1초를 1천만 번으로 잡습니다. 한계선에 아슬아슬하게 닿는 방법은 고르지 않습니다.
횟수는 반복문이 센다
다음을 눌러 한 줄씩 넘기며 count 가 오르는 걸 보세요.
다음을 눌러 한 줄씩 넘겨 보세요
n = 4
- 1def has_duplicate(arr):
- 2 n = len(arr)
- 3 count = 0
- 4 for i in range(n):
- 5 for j in range(i + 1, n):
- 6 count += 1
- 7 if arr[i] == arr[j]:
- 8 return True
- 9 return False
count += 1— 한 쌍을 견줄 때마다 1 오른다range(i + 1, n)— 앞에서 본 쌍은 다시 안 본다- 끝나면 — 4칸에서 6번. N(N−1)/2 이라 N² 으로 친다
번호표가 100만 장입니다. 모두와 모두를 견주는 방법(N²)은 ③ 표에서 어떻게 나올까요?
한 줄이어도 한 번이 아니다
x in arr— 리스트에서는 앞에서부터 N 번 훑는다. 반복문 안에 두면 N²arr.pop(0)— 나머지 칸을 전부 한 칸씩 당긴다. N 번sorted(arr)— 한 줄이지만 N log N 이다
같은 값을 일찍 찾으면 빨리 끝납니다. 그래도 제한 시간은 가장 운이 나쁜 입력으로 어림합니다.
문제에서 이 말이 보이면
다음 장에서는 자기 안에서 자기를 다시 부르는 재귀를 봅니다.