시간 복잡도 (Time Complexity)

시간 복잡도(Time Complexity)는 알고리즘이 입력 크기에 따라 실행에 필요한 시간(또는 연산 횟수)의 증가율을 나타내는 개념이다. 즉, 알고리즘의 효율성을 평가하는 데 사용된다.

일반적으로 시간 복잡도는 입력 크기 n에 대한 함수로 표현된다. 가장 일반적으로 사용되는 표기법은 Big O 표기법이다. Big O 표기법은 알고리즘의 실행 시간 상한을 나타내며, 주어진 알고리즘의 실행 시간이 입력 크기에 따라 어떻게 증가하는지를 나타낸다.

---

입력 데이터 수에 따른 시간 복잡도

최대 시간이 1초일 때 입력 데이터 수에 따른 시간 복잡도는 다음과 같다.

입력 데이터 수	시간 복잡도
1,000	O(n^2) 이하
10,000	O(n^2) 미만 (최대한 적게)
100,000	O(nlogn) 이하
1,000,000	O(nlogn) 미만 (가급적 O(n))
그 이상	문제의 조건 살펴보기, 특정 알고리즘 사용

---

시간 복잡도 줄이기

1. readline() 사용

import sys
data = sys.readline()

2. string operation

string_list = ["a", "b", "c"]
result = ""

# 사용하지 말기
for c in string_list:
	result = result + c

# 가급적 join() 사용
result = "".join()