[Algorithm 이론#1] 시간복잡도, 점근적 표기법

1. 시간 복잡도란? 

알고리즘의 성능을 평가할 때 '실행 시간'을 스톱워치로 재는 것은 무의미합니다. 

컴퓨터의 하드웨어 성능, 운영체제 상태 등에 따라 매번 결과가 달라지기 때문입니다. 

 

따라서 컴퓨터 공학에서는 입력 데이터의 크기(N)가 증가함에 따라 프로그램의 '연산 횟수'가 얼마나 

가파르게 증가하는지를 수학적인 함수로 나타냅니다. 이것이 바로 시간 복잡도입니다. 

 

시간 복잡도 = 데이터 크기에 따른 연산 횟수의 증가 비율

 

---

2. 점근적 표기법

연산 횟수를 정확한 수식 (예 :  3N^2 + 5N + 2)으로 표현할 수도 있지만, N이 무한히 커질 때는 최고차항 외의

값들은 영향력이 미미해집니다. 

 

따라서 가장 지배적인 항만 남겨서 함수의 한계(Bound)를 표현하는 방식을 접근적 표기법이라고 합니다.  

 

표기법	기호	의미	특징
빅오	O(n)	최악의 경우( Uppoer Bound)	아무리 느려도 이 시간 안에는 끝난다.  (알고리즘에서 가장 중요하게 사용됨)
빅오메가	Ω(n)	최선의 경우(Lower Bound)	최소한 이만큼의 시간은 걸린다
빅세타	θ(n)	평균/정확한 한계(Tight Bound)	상한선과 하한선이 일치할 때 사용

 

1. 빅오 - "아무리 최악이어도 이 시간 안에는 끝납니다"

• 의미 : 상한선 / 최악의 경우
• 언제 사용하나요?
  • 알고리즘 풀이 :
    채점 시스템은 가장 극단적이고 까다로운 데이터를 입력하여 코드를 괴롭힙니다. 따라서 "내 코드는 최악의 데이터가 들어와도 제한 시간(1초) 안에 무조건 통과한다"는 것을 보장할 때 사용합니다. 
  • 실무 서비스 개발 :
    서버가 트래픽 폭주를 견딜 수 있는지 평가할 때 가장 안전하고 보수적인 기준이 됩니다. 실무 개발자들이 시간 복잡도를 말할 때 99%는 빅오 표기법을 의미합니다.
• 비유 : "출근길 차가 아무리 막혀도, 10시 전에는 무조건 회사에 도착합니다."

 

2. 빅오메가 - "아무리 운이 좋아도 최소한 이 시간은 걸립니다"

• 의미 : 하한선 / 최선의 경우
• 언제 사용하나요?
  • 알고리즘의 이론적 한계를 증멸할 때 :
    주로 컴퓨터 과학 이론이나 논문에서 사용합니다. 예를 들어 "데이터를 서로 비교해서 정렬하는 알고리즘은 아무리 천재적으로 만들어도 최소 Ω(nlogn)의 연산은 무조건 필요하다"라고 수학적 한계를 그어버릴 때 씁니다.
  • 더 이상의 최적화가 불가능함을 알릴 때 :
    "이미 최적의 상태에 도달했으니, 여기서 더 빠르게 만들려는 시도는 시간 낭비다"라는 것을 증명할 때 유용합니다.
• 비유 : "비행기를 타고 날아가도, 서울에서 부산까지 물리적으로 최소 1시간은 무조건 걸립니다.

 

3. 빅세타 - "언제나 딱 이만큼의 시간이 걸립니다."

• 의미 : 정확한 한계 / 상한과 하한이 일치할 때
• 언제 사용하나요?
  • 가장 정확한 성능 분석이 필요할 때 : 
    알고리즘의 최선의 경우와 최악의 경우가 동일하거나, 그 차이가 무의미할 정도로 비슷할 때 사용합니다.
  • 엄밀한 학술 분석 : 
    빅오는 '상한선'이기 때문에, 1초 걸리는 코드를 O(100년)이라고 말해도 수학적으로 틀린 말은 아닙니다만. 이렇게 느슨하게 과장해서 표현하는 것을 막고, "적확히 N^2의 비율로 증가한다"고 콕 집어 말하고 싶을 때 세타를 사용합니다. 
• 비유 : 새벽이든 출퇴근 시간이든, 지하철을 타면 언제나 정확히 45분 걸립니다.

 

---

 

3. 빅오 표기법의 수학적 계산법

빅오 표기법 O(n)은 단순히 "최고차항만 남긴다"는 암기식이 아니라, 수학적인 증명 과정을 거칩니다.

 

어떤 함수 f(n)이 O(g(n))에 속한다는 것은 다음 부등식을 만족하는 양의 상수 c와 n0가 존재한다는 뜻입니다.

 

$$f(n) \le c \cdot g(n) \quad (단, n \ge n_0)$$

 

각 변수의 의미

• f(n) : 직접 작성한 코드의 실제 연산 횟수 (예 : a1n + a0)
• g(n) : 기준이 되는 점근 함수 (예 : n, n2)
• c : g(n)의 기울기나 폭을 조절하여 f(n)을 덮어버릴 수 있게 만드는 상수 
• n0 : 이 부등식이 항상 성립하기 시작하는 n의 최소 기준점

출처(https://thebook.io/080200/0022/)

계산 예시

• f(n) = 2n+3 이 O(n)인지 증명해봅니다. 
  • 목표 : 2n+3 <= c·n 을 만족하는 c와 n0찾기
  • 우변의 기울기 c가 좌변의 기울기 2보다 커야, 양수인 상수항(+3)을 극복하고 언젠가 좌변을 덮을 수 있습니다.(c > 2)
  • c = 3이라고 가정해 보면, 부등식은 2n + 3 <= 3n 이 됩니다.
  • 양변에서 2n 을 빼서 식을 정리하면 3 <= n 이 됩니다. 즉, n이 3 이상일 때부터 이 부등식은 항상 참이 됩니다.
  • 따라서 c = 3, n0 = 3으로 설정하면, n >= 3 인 모든 양수 n에 대해 부등식이 완벽하게 성립하므로 2n + 3 은 수학적으로 O(n)에 속한다고 증명할 수 있습니다.

---

4. 자주 쓰이는 시간 복잡도

• O(1) : (상수 시간) 데이터 크기와 무관하게 즉시 처리 (수식 계산 배열 인덱스 접근)
• O(log N) : (로그 시간) 데이터를 반씩 쪼개며 탐색 (이진 탐색)
• O(N) : (선형 시간) 데이터 크기만큼 1차원적으로 비례해서 증가 (1중 for문)
• O(N log N) : (선형 로그 시간) 효율적인 정렬 알고리즘 (파이썬의 내장 sort())
• O(N^2) : (이차 시간) 2중 for문 등 데이터가 커지면 기하 급수적으로 느려짐

---

5. 실전 알고리즘 팁

알고리즘 문제에서 제한 시간이 1초라면, 파이썬 기준으로 약 2,000만 번(20,000,000)의 연산이 가능하다고 역산하여 접근해야 합니다.

• 입력값 N이 100,000이라면?
  • O(N^2) 알고리즘을 쓰면 100억 번 연산 > 시간 초과 
  • O(N log N) 이하의 알고리즘으로 풀어야 통과
• 입력값 n이 1,000이라면?
  • O(N^2) 알고리즘을 써도 100만 번 연산 > 2중 for문으로 풀어도 무난하게 통과합니다.

1. 알고리즘의 절대 기준 : C/C++ (1초 = 1억번)
백준이나 프로그래머스 같은 온라인 저지 시스템은 기본적으로 C/C++ 언어를 기준으로 채점 서버를 세팅합니다.
C/C++은 코드를 컴퓨터가 바로 알아들을 수 있는 기계어로 완벽하게 번역해 놓고 실행하는 컴파일 언어이기 때문에 속도가 상당히 빠릅니다. 통상적으로 C/C++은 1초에 약 1억번의 단순 연산을 한다고 계산합니다.

2. 파이썬은 왜 더 느릴까? (인터프리터 언어의 한계)
반면, 파이썬은 코드를 한 줄 한 줄 읽어가며 실시간으로 기계어로 번역해서 실행하는 인터프리터 언어입니다. 
게다가 변수에 자료형을 미리 지정하지 않고 실행 중에 알아서 판단하는 기능(동적 타이핑)까지 들어 있습니다. 
이런 편의성 때문에 개발자가 코드를 짜기는 엄청나게 편하지만, 컴퓨터 입장에서는 실행할 때마다 이것 저것 확인해야 할 게 많아서 C/C++보다 속도가 훨씬 느립니다.

3. 그래서 나온 안전빵 계산법 (1억 / 2000만)
일반적으로 파이썬의 단순 반복문 연산 속도는 C/C++에 비해 대략 5배에서 길게는 10배 정도 느리다고 평가합니다.