///
Search

μ‹œκ°„μ œν•œ & λ©”λͺ¨λ¦¬μ œν•œ

λΆ„λ₯˜
속성
생성일
2022/03/30 13:21
μ΅œμ’… μˆ˜μ •
2022/03/30 13:55

μ‹œκ°„μ œν•œ

파이썬 κΈ°μ€€ μ‹œκ°„μ œν•œ 1초 λ‹Ή μ—°μ‚° 2,000만 번 정도 κ°€λŠ₯ν•˜λ‹€κ³  ν•˜λŠ”λ°
κ·Έλ³΄λ‹€λŠ” 쑰금 μ—¬μœ λ‘­κ²Œ μž‘μ•„μ„œ 1초 λ‹Ή μ—°μ‚° 1μ–΅(10^8) 번으둜 봐도 λœλ‹€κ³  ν•œλ‹€.
데이터 개수(N)
μ‹œκ°„λ³΅μž‘λ„
10^7 (천만) 이상
O(n) , O(logn) ..
10^5 (μ‹­λ§Œ) ~ 10^6 (백만)
O(nlogn) ..
10^3 ~ 10^4
O(n^2) ..
100 ~ 500
O(n^3)
10 ~ 20
O(2^n), O(n * 2^n), O(n!)
μ‹œκ°„ λ³΅μž‘λ„λ₯Ό κ³ λ €ν•œ μ½”λ“œ 섀계 μ „λž΅
κ°œμš” μ•Œκ³ λ¦¬μ¦˜ λ¬Έμ œμ—λŠ” μ—¬λŸ¬ 가지 μ œν•œμ΄ μ£Όμ–΄μ§‘λ‹ˆλ‹€. μ—¬κΈ°μ—λŠ” μž…λ ₯으둜 μ£Όμ–΄μ§€λŠ” κ°’μ˜ λ²”μœ„, κ·Έ 값듀이 κ°€μ§€λŠ” μ„±μ§ˆ λ“±μ˜ 쑰건도 μžˆμ§€λ§Œ, λŒ€λΆ€λΆ„μ˜ 경우 λ©”λͺ¨λ¦¬ μ œν•œκ³Ό μ‹œκ°„ μ œν•œμ΄ 같이 μ£Όμ–΄μ§‘λ‹ˆλ‹€. λ§Žμ€ λ¬Έμ œλ“€μ—μ„œλŠ” 이 μ œν•œμ„ 크게 κ³ λ €ν•˜μ§€ μ•Šκ³ λ„ 닡을 μ°Ύμ•„λ‚΄λŠ” λ‘œμ§λ§Œμ„ μƒκ°ν•˜μ—¬ μ½”λ“œλ‘œ κ΅¬ν˜„ν•˜λ©΄ 톡과할 수 μžˆμ§€λ§Œ, 일뢀 λ¬Έμ œμ—μ„œλŠ” μ‹œκ°„ μ œν•œ λ•Œλ¬Έμ— 직관적인 ν•΄κ²°μ±…μœΌλ‘œλŠ” 톡과할 수 μ—†λŠ” κ²½μš°λ„ μ‘΄μž¬ν•©λ‹ˆλ‹€.
https://www.secmem.org/blog/2021/01/22/time-complexity/

λ©”λͺ¨λ¦¬μ œν•œ

int(4byte) κΈ°μ€€
int 데이터 개수(리슀트 길이)
λ©”λͺ¨λ¦¬ 크기
1,000 (10^3)
4KB
1,000,000 (10^6)
4MB
1,000,000,000 (10^9)
40MB
λŒ€μ²΄λ‘œ μ½”ν…Œμ—μ„œλŠ” 128~512MB 의 λ©”λͺ¨λ¦¬ μ œν•œμ΄ μ£Όμ–΄μ§€λ―€λ‘œ, int κΈ°μ€€ 전체 λ°μ΄ν„°μ˜ λ§₯μ‹œλ©ˆμ€ 10^9 개 μ •λ„λœλ‹€.