# [07-05] 상수 계수와 실제 성능
Big-O 표기법은 점근적 성능을 나타내지만, 실제 성능은 상수 계수, 캐시, 하드웨어 특성 등 여러 요인에 영향을 받습니다.
🎯 이론과 실제의 차이
Big-O의 한계
Big-O는 중요하지만 전부가 아닙니다.
실생활 비유:
두 개의 자동차:
자동차 A:
- 최고 속도: 200km/h (이론)
- 실제 평균: 60km/h (시내 주행)
자동차 B:
- 최고 속도: 150km/h (이론)
- 실제 평균: 80km/h (고속도로)
이론상 A가 빠르지만
실제로는 B가 더 빠를 수 있음!
→ 사용 환경이 중요!알고리즘 예시:
# 알고리즘 A: O(n)
def algorithm_a(arr):
result = 0
for i in range(len(arr)):
result += arr[i] * 1000 # 상수 계수 큼
result += compute_heavy(arr[i])
result += another_operation(arr[i])
return result
# 알고리즘 B: O(n log n)
def algorithm_b(arr):
return efficient_sort(arr) # 최적화된 구현
# n = 1000일 때
# A: 1000번 × (무거운 연산 3개) ≈ 3초
# B: 1000 × log(1000) ≈ 10000번 × (가벼운 연산) ≈ 0.01초
# 이론: A가 빠름 (O(n) < O(n log n))
# 실제: B가 훨씬 빠름!왜 이론과 실제가 다른가?
Big-O가 무시하는 것들:
1. 상수 계수:
O(n) vs O(100n) → 둘 다 O(n)
실제로는 100배 차이!
2. 낮은 차수 항:
O(n² + 1000n) → O(n²)
n이 작으면 1000n이 중요!
3. 하드웨어 특성:
- 캐시 효율
- 메모리 접근 패턴
- CPU 파이프라인
4. 구현 품질:
- 최적화 수준
- 언어 특성
- 라이브러리 효율
5. 입력 크기:
n이 작으면 점근적 성능 의미 없음📏 상수 계수의 영향
상수 계수란?
상수 계수(Constant Factor)는 Big-O에서 무시되는 상수 배수입니다.
실제 시간 = c × f(n) + 낮은 차수 항
예:
T(n) = 5n² + 3n + 100
Big-O: O(n²)
하지만:
- 계수 5는 중요!
- 3n도 작은 n에서 중요!
- 100도 매우 작은 n에서 중요!상수 계수 비교
예시 1: 선형 탐색 vs 이진 탐색
import time
# 선형 탐색: O(n), 상수 작음
def linear_search(arr, target):
"""
실제 시간: 1 × n
간단한 연산
"""
for i in range(len(arr)):
if arr[i] == target: # 1번 비교
return i
return -1
# 이진 탐색: O(log n), 상수 큼
def binary_search(arr, target):
"""
실제 시간: 10 × log n
복잡한 연산 (인덱스 계산, 비교)
"""
left, right = 0, len(arr) - 1
while left <= right:
mid = (left + right) // 2 # 나눗셈
if arr[mid] == target:
return mid
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1
# 벤치마크
arr = list(range(100)) # n = 100
target = 99
# 선형 탐색: 100번 비교
# 이진 탐색: log₂(100) ≈ 7번, 하지만 각 비교가 복잡
# n이 작으면 선형이 더 빠를 수 있음!
# 교차점: n ≈ 50~100실제 측정:
import time
import random
def benchmark():
sizes = [10, 50, 100, 500, 1000, 5000]
for n in sizes:
arr = sorted(random.sample(range(n*10), n))
target = arr[-1] # 최악의 경우
# 선형 탐색 측정
start = time.perf_counter()
for _ in range(10000):
linear_search(arr, target)
linear_time = time.perf_counter() - start
# 이진 탐색 측정
start = time.perf_counter()
for _ in range(10000):
binary_search(arr, target)
binary_time = time.perf_counter() - start
print(f"n={n:5d}: 선형={linear_time:.4f}s, 이진={binary_time:.4f}s")
benchmark()
# 예상 출력:
# n= 10: 선형=0.0012s, 이진=0.0018s ← 선형이 빠름!
# n= 50: 선형=0.0058s, 이진=0.0045s ← 비슷
# n= 100: 선형=0.0115s, 이진=0.0048s ← 이진이 빠름
# n= 500: 선형=0.0580s, 이진=0.0051s ← 이진이 훨씬 빠름
# n= 1000: 선형=0.1160s, 이진=0.0054s
# n= 5000: 선형=0.5800s, 이진=0.0059s예시 2: 삽입 정렬 vs 병합 정렬
def insertion_sort(arr):
"""
시간: O(n²)
실제: c₁ × n² (c₁ 작음)
장점:
- 간단한 연산
- 캐시 친화적
- 오버헤드 작음
"""
for i in range(1, len(arr)):
key = arr[i]
j = i - 1
while j >= 0 and arr[j] > key:
arr[j + 1] = arr[j]
j -= 1
arr[j + 1] = key
def merge_sort(arr):
"""
시간: O(n log n)
실제: c₂ × n log n (c₂큼)
단점:
- 재귀 오버헤드
- 추가 메모리 할당
- 병합 연산 복잡
"""
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left = merge_sort(arr[:mid]) # 배열 복사 오버헤드
right = merge_sort(arr[mid:])
return merge(left, right) # 병합 오버헤드
# 교차점 계산:
# c₁ × n² = c₂ × n log n
# n = c₂/c₁ × log n
# 실제 측정 결과:
# c₁ ≈ 0.1, c₂ ≈ 2
# 교차점: n ≈ 40~60
# n < 50: 삽입 정렬이 빠름
# n > 50: 병합 정렬이 빠름
# Python의 Timsort:
# → 작은 부분은 삽입 정렬 사용!💾 캐시와 메모리 지역성 (Locality)
메모리 계층 구조
속도 용량 비용
빠름 ↑ 비쌈 ↑
레지스터 수십 바이트 매우 비쌈
L1 캐시 32-64KB 비쌈
L2 캐시 256KB-512KB 비쌈
L3 캐시 8-32MB 중간
RAM 8-64GB 저렴
SSD 256GB-2TB 저렴
HDD 1-10TB 매우 저렴
느림 ↓ 많음 ↓ 싸짐 ↓
접근 시간:
레지스터: 1 사이클
L1 캐시: 3-4 사이클
L2 캐시: 10-20 사이클
L3 캐시: 40-75 사이클
RAM: 200-300 사이클
SSD: 100,000 사이클
HDD: 10,000,000 사이클
→ 캐시 히트/미스가 성능에 큰 영향!
1. 캐시 히트 (Cache Hit) : CPU가 참조하고자 하는 데이터가 캐시 메모리에 이미 존재할 때
2. 캐시 미스 (Cache Miss) : CPU가 찾는 데이터가 캐시 메모리에 없어서, RAM이나 SSD/HDD까지 가서 데이터를 가져와야 하는 상황
<참고: 사이클>
1. 물리적 의미: 전기적 '박동' (The Pulse)
CPU 내부에는 수정 진동자(Quartz Crystal)가 일정하게 전기 신호를 보냄.
이 신호가 0(Low)에서 1(High)로 올라갔다가 다시 0으로 내려오는 한 번의 파동이 바로 1 사이클임.
이 박동이 없으면 CPU 내부의 데이터는 이동하거나 변할 수 없음. 즉, 모든 동작의 '메트로놈' 역할
2. 행동 단위로서의 의미: 명령어의 '한 걸음'
CPU가 명령어를 처리하려면 보통 4단계의 과정을 거침(가져오기(Fetch) → 해석(Decode) → 실행(Execute) → 저장(Writeback))
각 단계는 최소 1 사이클이 필요. 1 사이클 동안 "레지스터에 있는 숫자 A를 가져와라"라는 아주 작은 단위의 행동 하나를 수행
3. 접근 시간(Latency)에서의 의미: "CPU가 데이터를 기다리며 허비하는 박동 수"
L1 캐시(4 사이클)은 CPU가 "데이터 줘!"라고 외친 뒤, 심장이 4번 뛸 동안 아무것도 못 하고 기다려야 데이터가 도착한다는 의미
* 현대 CPU는 이 기다리는 시간이 아까워서, 데이터를 기다리는 동안(사이클이 낭비되는 동안)
순서와 상관없이 할 수 있는 다른 일부터 먼저 처리하는 '비순차적 실행(Out-of-Order Execution)' 기술을 사용지역성의 원리
지역성(Locality)이란?
지역성은 프로그램이 특정 시간에 메모리의 특정 부분만 집중적으로 접근하는 경향을 말합니다.
프로그램의 메모리 접근 패턴:
무작위 접근 (지역성 없음):
메모리: [A] [B] [C] [D] [E] [F] [G] [H]
접근: ↑ ↑ ↑ ↑ ↑
A → D → B → F → C
→ 메모리 전체를 골고루 접근
지역적 접근 (지역성 있음):
메모리: [A] [B] [C] [D] [E] [F] [G] [H]
접근: ↑ ↑ ↑
A → B → C → B → A
→ 특정 영역만 집중 접근왜 지역성이 중요한가?
캐시의 작동 원리:
1. 자주 쓰는 데이터를 빠른 메모리(캐시)에 복사
2. 다음 접근 시 캐시에서 가져옴 (빠름!)
3. 지역성이 높으면 → 캐시 히트 많음 → 빠름
4. 지역성이 낮으면 → 캐시 미스 많음 → 느림
캐시 히트: 0.5ns (매우 빠름)
캐시 미스: 100ns (200배 느림!)지역성의 두 가지 종류:
프로그램의 지역성은 크게 시간적 지역성과 공간적 지역성으로 나뉩니다.
1. 시간적 지역성(Temporal Locality)
정의: 최근에 접근한 데이터를 가까운 미래에 다시 접근하는 경향
예:
for i in range(n):
sum += arr[i] # arr[i]는 한 번만 접근
for i in range(n):
for j in range(n):
sum += matrix[i] # matrix[i]를 n번 재사용!
# 캐시에 유리2. 공간적 지역성(Spatial Locality)
정의: 접근한 데이터 근처의 데이터를 곧 접근하는 경향
예:
# 좋은 예: 순차 접근
for i in range(n):
sum += arr[i] # 연속된 메모리 접근
# 캐시 라인 활용
# 나쁜 예: 임의 접근
for i in random_indices:
sum += arr[i] # 불연속 접근
# 캐시 미스 많음캐시 친화적 코드
예시 1: 행렬 순회
import numpy as np
import time
# 나쁜 예: 열 우선 순회 (Python)
def column_major(matrix):
"""
캐시 비친화적
Python/C는 행 우선 저장 → 열 순회는 캐시 미스 많음
"""
n = len(matrix)
total = 0
for col in range(n):
for row in range(n):
total += matrix[row][col] # 불연속 접근!
return total
# 좋은 예: 행 우선 순회
def row_major(matrix):
"""
캐시 친화적
연속된 메모리 접근 → 캐시 히트 많음
"""
n = len(matrix)
total = 0
for row in range(n):
for col in range(n):
total += matrix[row][col] # 연속 접근!
return total
# 벤치마크
n = 5000
matrix = [[i + j for j in range(n)] for i in range(n)]
start = time.time()
column_major(matrix)
col_time = time.time() - start
start = time.time()
row_major(matrix)
row_time = time.time() - start
print(f"열 우선: {col_time:.4f}s")
print(f"행 우선: {row_time:.4f}s")
print(f"차이: {col_time / row_time:.2f}배")
# 예상 출력:
# 열 우선: 3.2456s
# 행 우선: 1.8234s
# 차이: 1.78배 ← 같은 O(n²)인데 78% 느림!예시 2: 데이터 구조 선택
# 배열 vs 연결 리스트
class Node:
def __init__(self, data):
self.data = data
self.next = None
# 연결 리스트: 캐시 비친화적
def sum_linked_list(head):
"""
노드들이 메모리에 흩어져 있음 → 캐시 미스 많음
"""
total = 0
current = head
while current:
total += current.data # 포인터 따라가기
current = current.next # 불연속 접근
return total
# 배열: 캐시 친화적
def sum_array(arr):
"""
연속된 메모리 → 캐시 히트 많음
"""
total = 0
for x in arr: # 연속 접근
total += x
return total
# 벤치마크 (n = 1,000,000)
# 연결 리스트: 0.15초
# 배열: 0.05초
# → 3배 차이! (둘 다 O(n))🔧 하드웨어 특성
CPU 파이프라인과 분기 예측
분기 예측(Branch Prediction):
*CPU가 if-else 같은 조건문(분기)의 결과(참/거짓)를 실제로 계산하기 전에 미리 추측하여 명령어를 파이프라인에 미리 실행하는 고속화 기술
import random
import time
# 예측 가능한 분기
def predictable_branch(arr):
"""
정렬된 배열: 분기 예측 성공
"""
count = 0
for x in arr:
if x < 50: # 처음엔 항상 True, x가 50 이후에는 항상 False
count += 1
return count
# 예측 불가능한 분기
def unpredictable_branch(arr):
"""
무작위 배열: 분기 예측 실패
"""
count = 0
for x in arr:
if x < 50: # True/False 무작위
count += 1
return count
# 벤치마크
n = 10_000_000
# 정렬된 배열
sorted_arr = list(range(100))
start = time.time()
predictable_branch(sorted_arr * (n // 100))
sorted_time = time.time() - start
# 무작위 배열
random_arr = [random.randint(0, 99) for _ in range(n)]
start = time.time()
unpredictable_branch(random_arr)
random_time = time.time() - start
print(f"정렬됨: {sorted_time:.4f}s")
print(f"무작위: {random_time:.4f}s")
print(f"차이: {random_time / sorted_time:.2f}배")
# 예상 출력:
# 정렬됨: 0.3245s
# 무작위: 0.8912s
# 차이: 2.75배 ← 같은 연산인데!SIMD (Single Instruction Multiple Data)
SIMD(단일 명령어, 다중 데이터)는 병렬 컴퓨팅 아키텍처의 한 유형으로 하나의 명령어로 여러 개의 데이터를 동시에 처리하는 기법
import numpy as np
import time
# 일반 반복문
def sum_python(arr):
"""
한 번에 하나씩 처리
"""
total = 0
for x in arr:
total += x
return total
# NumPy (SIMD 활용)
def sum_numpy(arr):
"""
한 번에 여러 개 처리 (벡터화)
CPU가 한 명령으로 4-8개 동시 처리
"""
return np.sum(arr)
# 벤치마크
n = 10_000_000
arr_python = list(range(n))
arr_numpy = np.arange(n)
start = time.time()
sum_python(arr_python)
python_time = time.time() - start
start = time.time()
sum_numpy(arr_numpy)
numpy_time = time.time() - start
print(f"Python: {python_time:.4f}s")
print(f"NumPy: {numpy_time:.4f}s")
print(f"차이: {python_time / numpy_time:.2f}배")
# 예상 출력:
# Python: 0.8234s
# NumPy: 0.0145s
# 차이: 56.78배 ← 둘 다 O(n)!📊 실제 벤치마크
정렬 알고리즘 실측
import time
import random
def benchmark_sorts(n):
"""
다양한 정렬 알고리즘 벤치마크
"""
# 테스트 데이터
data = [random.randint(0, 1000) for _ in range(n)]
algorithms = {
'Bubble': bubble_sort,
'Insertion': insertion_sort,
'Merge': merge_sort,
'Quick': quick_sort,
'Python': sorted # 내장 함수 (Timsort)
}
results = {}
for name, func in algorithms.items():
test_data = data.copy()
start = time.perf_counter()
func(test_data)
elapsed = time.perf_counter() - start
results[name] = elapsed
return results
# 다양한 크기로 테스트
for n in [100, 500, 1000, 5000]:
print(f"\nn = {n}:")
results = benchmark_sorts(n)
for name, time_val in sorted(results.items(), key=lambda x: x[1]):
print(f" {name:12s}: {time_val:.6f}s")
# 예상 출력:
# n = 100:
# Python : 0.000015s ← C로 구현, 최적화
# Quick : 0.000123s
# Merge : 0.000189s
# Insertion : 0.000234s ← n이 작아서 괜찮음
# Bubble : 0.000456s
# n = 1000:
# Python : 0.000234s
# Quick : 0.001567s
# Merge : 0.002134s
# Insertion : 0.021345s ← 급격히 느려짐
# Bubble : 0.043212s
# n = 5000:
# Python : 0.001345s
# Quick : 0.009876s
# Merge : 0.013456s
# Insertion : 0.523451s ← 매우 느림
# Bubble : 1.234567s ← 극도로 느림입력 패턴별 성능
def benchmark_patterns(sort_func):
"""
다양한 입력 패턴에서 성능 측정
"""
n = 10000
patterns = {
'무작위': [random.randint(0, 1000) for _ in range(n)],
'정렬됨': list(range(n)),
'역순': list(range(n, 0, -1)),
'거의 정렬': list(range(n)),
'중복 많음': [i % 10 for i in range(n)]
}
# 거의 정렬된 패턴 생성
patterns['거의 정렬'][::100] = [random.randint(0, n) for _ in range(n // 100)]
print(f"\n{sort_func.__name__}:")
for pattern_name, data in patterns.items():
test_data = data.copy()
start = time.perf_counter()
sort_func(test_data)
elapsed = time.perf_counter() - start
print(f" {pattern_name:12s}: {elapsed:.6f}s")
# 테스트
benchmark_patterns(insertion_sort)
benchmark_patterns(quick_sort)
benchmark_patterns(merge_sort)
# 예상 출력:
# insertion_sort:
# 무작위 : 0.523456s
# 정렬됨 : 0.001234s ← 최선의 경우!
# 역순 : 1.045678s ← 최악의 경우
# 거의 정렬 : 0.012345s ← 매우 빠름!
# 중복 많음 : 0.423456s
# quick_sort:
# 무작위 : 0.012345s
# 정렬됨 : 0.234567s ← 최악의 경우 (피벗 선택)
# 역순 : 0.245678s
# 거의 정렬 : 0.213456s
# 중복 많음 : 0.013456s
# merge_sort:
# 무작위 : 0.015678s
# 정렬됨 : 0.015234s ← 항상 일정!
# 역순 : 0.015987s
# 거의 정렬 : 0.015456s
# 중복 많음 : 0.015678s🎯 실무 최적화 전략
알고리즘 선택 가이드
def choose_sort_algorithm(data):
"""
상황에 맞는 정렬 알고리즘 선택
"""
n = len(data)
# 1. 크기별 선택
if n < 50:
return insertion_sort(data) # 작은 배열: 오버헤드 작음
# 2. 패턴 감지
if is_nearly_sorted(data):
return insertion_sort(data) # 거의 정렬: O(n)
# 3. 안정성 필요 여부
if stability_required:
return merge_sort(data) # 안정 정렬
# 4. 메모리 제한
if memory_limited:
return heap_sort(data) # 제자리 O(n log n)
# 5. 일반적인 경우
return quick_sort(data) # 평균 빠름
def is_nearly_sorted(data, threshold=0.05):
"""
거의 정렬되어 있는지 확인
"""
inversions = 0
n = len(data)
# 샘플링으로 확인 (전체 확인은 비용 큼)
sample_size = min(1000, n)
for i in range(sample_size - 1):
if data[i] > data[i + 1]:
inversions += 1
return inversions / sample_size < threshold마이크로 최적화
# 1. 함수 호출 오버헤드 줄이기
def slow_sum(arr):
"""
함수 호출 많음
"""
total = 0
for x in arr:
total = add(total, x) # 함수 호출 오버헤드
return total
def add(a, b):
return a + b
def fast_sum(arr):
"""
인라인 연산
"""
total = 0
for x in arr:
total += x # 직접 연산
return total
# 2. 불필요한 작업 제거
def slow_filter(arr):
"""
중복 계산
"""
result = []
for x in arr:
if is_prime(x): # 매번 계산
result.append(x)
return result
def fast_filter(arr):
"""
캐싱
"""
prime_cache = {}
result = []
for x in arr:
if x not in prime_cache:
prime_cache[x] = is_prime(x)
if prime_cache[x]:
result.append(x)
return result
# 3. 메모리 할당 줄이기
def slow_concat(strings):
"""
매번 새 문자열 생성
"""
result = ""
for s in strings:
result += s # O(n²) 시간!
return result
def fast_concat(strings):
"""
한 번에 결합
"""
return "".join(strings) # O(n) 시간프로파일링
프로그램의 시간 복잡도 및 공간(메모리), 특정 명령어 이용, 함수 호출의 주기와 빈도 등을 측정하는 동적 프로그램 분석의 한 형태
import cProfile # Python 내장 프로파일러
import pstats # 프로파일링 결과 분석 도구
def profile_function(func, *args):
"""
함수의 실행 시간과 호출 통계를 측정하는 프로파일러
func: 측정할 함수
*args: 함수에 전달할 인자들
Returns: 함수의 실행 결과
"""
# 1. 프로파일러 생성 및 시작
profiler = cProfile.Profile()
profiler.enable() # 측정 시작
# 2. 함수 실행 (이 구간이 측정됨)
result = func(*args)
# 3. 측정 종료
profiler.disable()
# 4. 결과 분석 및 출력
stats = pstats.Stats(profiler)
stats.sort_stats('cumulative') # 누적 시간 순으로 정렬
stats.print_stats(10) # 상위 10개 함수만 출력
return result
# 사용 예시
def slow_algorithm(n):
"""
성능 측정을 위한 느린 알고리즘
O(n²) 시간복잡도
"""
result = []
for i in range(n):
for j in range(n):
result.append(i * j) # n² 번 호출
return result
# 프로파일링 실행
profile_function(slow_algorithm, 1000)
# 출력 결과 해석:
"""
ncalls tottime percall cumtime percall filename:lineno(function)
1 0.234 0.234 0.567 0.567 script.py:45(slow_algorithm)
1000000 0.156 0.000 0.156 0.000 {method 'append'}
1 0.089 0.089 0.089 0.089 {range}
컬럼 의미:
---------------------------------------------------------------------------
ncalls: 함수가 호출된 횟수. 예: slow_algorithm은 1번, append는 1,000,000번 호출됨
tottime: 이 함수 자체에서 소요된 시간 (하위 함수 호출시간 제외). 예: slow_algorithm 자체 로직은 0.234초
percall: 호출 1회 당 평균시간 (tottime / ncalls). 예: append 1회 당 0.000000156초 (매우 빠름)
cumtime: 이 함수와 하위 함수 호출을 모두 포함한 총 시간. 예: slow_algorithm 전체는 0.567초
percall: 호출 1회 당 누적 평균시간 (cumtime / ncalls)
filename:lineno(function): 함수의 위치. 예: script.py 파일 45번째 줄의 slow_algorithm 함수
분석:
-----
1. slow_algorithm이 0.567초 소요 (전체 시간)
2. append가 1,000,000번 호출되어 0.156초 소요 → 병목! append 호출을 줄이면 빨라짐
3. 개선 방법: 리스트 컴프리헨션 사용
result = [i * j for i in range(n) for j in range(n)]
"""💡 실무 팁
조기 최적화의 함정
# 잘못된 접근
def premature_optimization():
"""
"이 부분이 느릴 것 같으니 미리 최적화하자"
문제:
- 실제로 느린지 모름
- 복잡도만 증가
- 유지보수 어려움
"""
# 복잡한 최적화 코드...
pass
# 올바른 접근
def measure_then_optimize():
"""
1. 먼저 간단하게 구현
2. 프로파일링으로 병목 찾기
3. 병목만 최적화
"""
# 1. 간단한 구현
def simple_version():
pass
# 2. 측정
# ... 프로파일링 ...
# 3. 필요한 부분만 최적화
def optimized_critical_path():
pass실측의 중요성
# 항상 실제 측정하기
import timeit # timeit: 소규모 코드 조각이나 함수의 실행시간을 정확하게 측정, 성능을 비교 분석하는 데 사용
def compare_implementations():
"""
여러 구현 비교
"""
# 방법 1
time1 = timeit.timeit(
'sum(range(1000))',
number=10000
)
# 방법 2
time2 = timeit.timeit(
'total = 0\nfor i in range(1000): total += i',
number=10000
)
print(f"방법 1: {time1:.4f}s")
print(f"방법 2: {time2:.4f}s")
# 예상과 다를 수 있음!
# 내장 함수가 최적화되어 있을 수도🎯 핵심 정리
이론 vs 실제
Big-O의 한계:
- 상수 계수 무시
- 낮은 차수 항 무시
- 하드웨어 특성 무시
실제 성능 요인:
- 상수 계수 (10 ~ 100배 차이)
- 캐시 효율 (2 ~ 10배 차이)
- 하드웨어 특성 (2 ~ 100배 차이)
- 구현 품질상수 계수의 중요성
같은 O(n)도:
- 구현에 따라 10배 차이
- 언어에 따라 100배 차이
- 최적화에 따라 1000배 차이
교차점:
- 삽입 vs 병합: n ≈ 50
- 선형 vs 이진: n ≈ 100캐시와 메모리
지역성 원리:
- 시간적: 최근 접근 재사용
- 공간적: 인접 데이터 접근
캐시 친화적:
- 순차 접근
- 배열 우선
- 행 우선 순회실무 가이드
최적화 순서:
1. 올바른 알고리즘 선택
2. 프로파일링으로 병목 찾기
3. 병목만 최적화
4. 측정하여 검증
"조기 최적화는 만악의 근원"
- Donald Knuth벤치마크 필수
이론으로 예측 X
실제로 측정 O
도구:
- timeit (Python)
- cProfile (프로파일링)
- perf (Linux)🔗 다음 글에서는
[07-06] 상각 분석 (Amortized Analysis)
- 상각 분석의 개념: 연속된 연산의 평균 비용 계산
- 집계 방법: 전체 비용을 연산 횟수로 나누기
- 회계 방법: 크레딧 개념을 이용한 분석
- 포텐셜 방법: 잠재 함수를 이용한 엄밀한 증명
이전 글: [07-04] 최선/평균/최악 경우 분석
다음 글: [07-06] 상각 분석
시리즈: P1. Computer Science
AI 전문가를 꿈꾸는 도전자