알고리즘 복잡도 (Algorithmic Complexity)

알고리즘 복잡도(algorithmic complexity)는 입력 크기 n이 커질 때 알고리즘이 필요로 하는 계산 시간(시간 복잡도)이나 메모리(공간 복잡도)가 얼마나 빠르게 증가하는지를 나타내는 척도입니다. 보통 상수배를 무시한 점근 표기 O(·)로 표현합니다. (정보 이론의 '알고리즘적 복잡도', 즉 콜모고로프 복잡도와는 다른 개념입니다.)

자세히 알아보기

대표적인 증가율은 O(1) 상수, O(log n) 로그, O(n) 선형, O(n log n), O(n²) 이차, O(2ⁿ) 지수 시간입니다. n이 100만일 때 O(n log n)은 약 2,000만 번 정도의 연산이지만, O(n²)은 1조 번이 됩니다. 최악·평균·최선의 경우를 구분하며, O는 상한, Ω는 하한, Θ는 정확한 증가율을 뜻합니다.

복잡도 이론은 문제 자체의 난이도도 분류합니다. 다항 시간에 풀 수 있는 문제(P), 답을 다항 시간에 검증할 수 있는 문제(NP) 등이 있습니다. 다만 암호에 필요한 것은 '최악의 경우 어렵다'가 아니라 '무작위로 고른 거의 모든 경우에 어렵다'는 평균적 난이도이므로, NP-완전성만으로 암호를 만들지는 않습니다.

블록체인·암호화폐에서는

• 안전성 수준: 암호의 강도는 '가장 좋은 공격의 복잡도'로 표현합니다. 128비트 안전성은 약 2¹²⁸번의 연산이 필요하다는 뜻입니다. 비트코인 secp256k1의 이산 로그는 폴라드 로 방법으로 약 √n ≈ 2¹²⁸번 연산이 필요해 128비트 안전성을 가집니다.
• 양자 위협: 쇼어 알고리즘은 인수분해와 이산 로그를 다항 시간에 풀어 RSA·ECDSA의 복잡도 가정을 무너뜨립니다. 그로버 알고리즘은 무차별 탐색을 √ 수준으로 줄여 대칭 키의 안전성 비트를 절반으로 만들기 때문에, 장기 보안에는 AES-256처럼 긴 키를 권장합니다.
• 가스 비용: 이더리움의 가스는 연산의 실제 비용을 반영하도록 매겨집니다. 반복문이 사용자 입력 크기에 비례(O(n))하는 컨트랙트는 데이터가 쌓이면 블록 가스 한도를 넘어 실행 불가 상태가 될 수 있습니다.
• 영지식 증명: SNARK는 증명 크기와 검증 시간이 계산 크기와 거의 무관(상수 또는 로그 수준)하다는 복잡도 특성 덕분에 롤업에 쓰입니다.

쉽게 말하면

알고리즘 복잡도는 '일의 양이 두 배가 되면 시간이 두 배가 되는지, 네 배가 되는지, 아니면 폭발하는지'를 알려 주는 성장 곡선입니다.

예시

정렬된 100만 개 목록에서 이진 탐색은 최대 약 20번(log₂10⁶) 비교면 되지만, 처음부터 하나씩 찾으면 최대 100만 번 비교합니다.