Big O 표기법 과 알고리즘 성능 평가 이해하기

알고리즘 관련 공부를 진행하기 전에 왜 알고리즘 공부를 해야하는지에 대해서 짚고 넘어가면 좋을 것 같아 

블로그 글을 작성하게 되었다.

 

예를 들어 같은 문제를 푸는 두 개의 프로그램이 있다고 가정해보았을때 

하나는 1초만에 결과를 내고, 다른 하나는 10분이 걸린다고 해보자, 둘다 정답을 도출하지만 실문에서는 전혀 다른 평가를 

받을 것이다. 이 차이를 만들어 내는 것이 바로 알고리즘의 효율성이다.

효율적인 알고리즘은 더 적은 컴퓨팅 자원을 사용하면서 빠르게 결과를 도출할 수 있고, 이는 곧 서버 비용 절감과 

사용자 경험 향상으로 이어질 수 있다.

특히 대규모 데이터를 처리하는 환경에서는 이 차이로 인해 결과가 극적으로 벌어질 수 있을 것이다.

데이터 1000건을 처리할 때 0.01초 차이였던 것이, 1000만 건이 되면 몇 시간 vs 몇 초의 차이가 될 수도 있다.

때문에 알고리즘을 잘 짜는 것은 확연한 결과 차이를 위해서는 필요한 것이고 공부해야하는 것이다. 

 

그렇다면 알고리즘이 얼마나 효율적이라는 것을 객관적으로 어떻게 평가할 수 있을까?

내 컴퓨터에서만 빨리 돌아간다고 해서 해당 알고리즘이 잘 짜여진 알고리즘이라고 평가할수는 없다.

컴퓨터 사양, 프로그래밍 언어, 운영체제에 따라 실행 시간은 천차만별이기 때문이다.

그래서 하드웨어에 독립적이면서 입력 크기에 따른 성능 변화를 수학적으로 표현하는 방법이 필요하다.

이것이 바로 Big O 표기법이다.

---

Big O 표기법이란?

빅오(Big O) 표기법은 입력 크기 n이 충분히 커졌을 때, 알고리즘의 연산 횟수 (또는 메모리 사용량)가 

어떤 비율로 증가하는지 나타내는 접근적 표기법이다.

 

핵심은 증가율 에 집중한다는 것이다. 상수 계수나 낮은 차수 항은 n이 커지면 영향력이 미미해지기 때문에 생략한다.

예를 들어 실제 연산 횟수가 3n² + 5n + 100 이라고 가정해보았을때

(1) n = 10 일때 -> 3(100) + 5(10) + 100 = 450 → 제일 높은 차수의 n² 항이 전체의 약 67%

(2) n = 1,000 일때 -> 3(1,000,000) + 5(1,000) + 100 = 3,005,100 → n² 항이 전체의 약 99.8%

(3) n = 100,000일 때: n² 항의 비중은 99.9999% 이상

 

 

입력 크기인 n이 커질수록 5n + 100은 무의미해지고, 상수 3도 증가율 자체를 바꾸지 못한다. 

그래서 가장 높은 차수만 남기고, 계수 및 상수는 과감하게 버리게 되는 것이다.

따라서 n² 에 대한 부분만 명시해도 알고리즘의 성능을 충분히 표기할수 있다는 이야기가 된다.

이런 의미를 잘 담는 표기법이 Big O 표기법이다. 

결과적으로 실제 연산 횟수를 계산한 결과가 3n² + 5n + 100 인것을 Big O 표기법을 이용하면 

O(n²)의 형태로 간단하게 표기할 수 있는 것이다. 

 

Big O로 측정하는 두 가지 : 시간 복잡도와 공간 복잡도

빅오 표기법이 "증가율을 나타내는 도구"라는 건 알겠는데, 그래서 무엇의 증가율을 측정하는 걸까?

알고리즘 성능은 두가지 축으로 평가하게 된다.

 

1. 시간 복잡도 ( Time complexity )

입력 크기가 커질 때 연산 횟수가 얼마나 증가하는지를 나타낸다.

=> 이 알고리즘이 얼마나 오래 걸리는가? 에 대한 답이다.

여기서 주의할 점은, 시간 복잡도는 초 단위의 실제 실행 시간이 아니라 연산 횟수의 증가율이라는 것이다.

같은 O(n) 알고리즘이라도 C++에서는 0.1초, Python에서는 1초가 걸릴 수 있다.

하지만 둘 다 입력이 10배가 되면 시간도 약 10배가 된다는 점은 동일하다. 이 "10배가 되면 10배"라는 증가 패턴을 표현하는 것이 시간 복잡도이다.

 

2. 공간 복잡도 ( Space complexity )

입력 크기가 커질 때 추가로 필요한 메모리가 얼마나 증가하는지를 나타낸다.

=> 이 알고리즘이 메모리를 얼마나 쓰는가?에 대한 답이다.

여기서는 추가 라는 단어가 중요하다. 입력 데이터 자체가 차지하는 공간은 제외하고, 알고리즘이 문제를

풀기 위해 별도로 사용하는 메모리만 계산하게 된다.

 

# 시간 O(n), 공간 O(n) — 새 배열을 만들어서 반환
def reverse_copy(arr):
    return arr[::-1]

# 시간 O(n), 공간 O(1) — 추가 배열 없이 제자리 교환
def reverse_inplace(arr):
    left, right = 0, len(arr) - 1
    while left < right:
        arr[left], arr[right] = arr[right], arr[left]
        left += 1
        right -= 1

예를 들어 두 함수 모두 배열을 뒤집는 같은 결과는 내지만, reverse_copy는 n개 짜리 새 배열을 만들어야 하므로 

공간 O(n) 이고, reverse_inplace는 포인터 두개만 사용하므로 공간 O(1)이다.

 

왜 둘 다 알아야 하는가?

실제 서비스를 운영하다 보면 시간 복잡도와 공간 복도가 곧 비용으로 직결된다는 것을 체감하게 된다.

시간 복잡도가 높은 알고리즘은 서버의 CPU를 오래 점유한다. 그리고 API 응답이 느려지면 사용자는 이탈하게 되고,

동시 요청이 몰리면 서버가 버티질 못한다.

공간 복잡도가 높은 알고리즘은 메모리를 많이 잡아먹는다. 클라우드 환경에서는 메모리도 곧 요금이고 한계를 넘으면

서비스가 죽게 된다. 

결국 시간은 서버 응답 속도와 처리량, 공간은 인프라 비용과 안정성에 직결된다.

그리고 현실에서는 둘 중 하나만 좋으면 되는게 아니라, 상황에 따라 어느 쪽을 희생할지 판단해야 한다.

이것을 시간-공간 트레이드 오프 (Time-Space Tradeoff) 라고 한다.

 

(1) 메모리를 써서 시간을 버는 경우 

대표적인 경우가 캐싱이다. Redis에 조회 결과를 저장해두면 메번 DB에 요청하지 않아도 된다.

메모리 비용은 들지만 응답 속도가 수십 배 빨라지고, DB 부하도 줄어든다. 실시간 응답이 중요한 서비스라면 당연히 이쪽을 택한다.

 

(2) 시간을 써서 메모리를 아끼는 경우

모바일 앱이나 IoT 디바이스처럼 메모리가 제한된 환경에서는 반대이다.

데이터를 전부 메모리에 올리지 못하니까 느리더라도 필요할 때 마다 디스크에서 읽어오는 방식을 택한다.

대용량 로그 파일을 처리할 때 파일 전체를 메모리에 올리는 대신 한 줄씩 스트리밍으로 읽는 것도 같은 맥락이다. 

 

이처럼 시간 복잡도와 공간 복잡도를 둘 다 이해하고 있어야 서비스의 요구사항에 맞는 적절한 선택을 할 수 있다.

무조건 빠른 게 좋다 가 아니라, 주어진 제약 조건 안에서 최적의 경우를 찾는 것이 실무에서의 알고리즘 설계라고 할 수 있다.

---

주요 시간 복잡도 한눈에 보기

그럼 이제 실제로 어떤 것들이 있는지 알아 보려고 한다.

예를 들어 어떤 알고리즘이 O(n log n) 이다 라는 말을 들었을때 그게 빠른건지 느린건지 감이 와야

트레이드 오프 판단을 할 수 있기 때문이다.

 

아래는 자주 등장하는 시간 복잡도를 느린 순서대로 정리한 것이다. 

같은 입력 크기라도 복잡도에 따라 연산 횟수가 얼마나 달라지는지 위주로 보면 좋을 것 같다.

(1) O(1) - 상수시간

입력이 아무리 커져도 실행 시간이 변하지 않는다.

배열에서 인덱스로 값을 꺼내거나, 해시맵에서 키로 조회하는 경우이다.

가장 이상적이지만, 모든 문제에 적용할 수 있는 것은 아니다.

 

(2) O(log n) - 로그시간

입력이 두배로 늘어도 연산은 딱 한번만 추가 된다. 이진 탐색이 대표적이다. 

100만 개의 데이터터에서 원하는 값을 찾는데 약 20번이면 충분하다.

 

(3) O(n) - 선형시간

입력 크기에 정비례한다. 배열을 처음부터 끝까지 한 번 순회하는 경우이다.

데이터가 10배 늘면 시간도 10배 늘어나므로 직관적으로 예측하기 쉽다.

 

(4) O(n²) — 이차 시간

이중 for문의 전형적인 패턴이다. 데이터가 10배 늘면 시간은 100배 늘어난다.

버블 정렬, 선택 정렬이 여기에 해당하며, 입력이 만 단위가 넘어가도 체감될 만큼 느려진다.

 

(5) O(n³) — 삼차 시간

삼중 반복문이나 행렬 곱셈에서 나타난다. n = 1,000이면 연산이 10억 번이므로, 실무에서는 가능하면 피하거나 최적화 알고리즘으로 대체한다.

(6) O(nⁿ) — 지수 이상

입력이 조금만 커져도 연산 횟수가 폭발한다. 그래프에서 보면 거의 수직으로 치솟는 곡선인데, 이론적으로는 존재하지만 현실에서는 쓸 수 없는 수준이다.

 

위 그래프를 보면 이 차이가 직관적으로 와닿게 된다.

입력이 작을 때는 복잡도 간 차이가 거의 없지만, 입력이 커질수록 곡선이 갈라지기 시작하면서 

O(n²) 이상은 급격하게 치솟는 것을 확인할 수 있다.

 

추가로 공간 복잡도도 같은 성장률 곡선을 따른다. 위 그래플프에서 Y축을 "Time" 대신 "Space"로 바꿔 읽으면 그대로

공간 복잡도 그래프가 된다. 

---

Big O 표기법은 결국 하나의 질문에서 출발하게 된다.

입력이 커지면 이 코드는 어떻게 되는가?

같은 결과를 내는 코드라도 입력이 커졌을 때 1초 만에 끝나는 코드가 있고, 10분이 걸리는 코드가 있다.

이 차이를 하드웨어나 언어에 의존하지 않고 객관적으로 표현하기 위해 Big O 표기법이 존재하는 것이다.

핵심은 간단하다.  상수, 낮은 차수항을 버리고 가장 빠르게 증가하는 항만 남기는것 

Big O가 측정하는 대상은 시간복잡도, 공간복잡도 2가지 이며 실무에서는 이 둘이 항상 트레이드 오프 관계에

놓이게 된다. 

O(1)부터 O(nⁿ) 까지 각 복잡도가 입력 크기에 따라 얼마나 다른 결과 양상을 띄는지를 확인해보았는데 

입력이 작을 때는 차이가 미미하지만, 커지는 순간 O(n²) 이상은 급격하게 치솟는다.

이 감각이 있어야 이 로직은 데이터가 늘어나면 병목이 되겠다는 판단을 코드 리뷰 단계에서 미리 할 수 있을 것이다.

 

미리 코드를 보고 이건 n이 커지면 문제가 되겠다, 여기서 메모리를 더 쓰면 시간을 줄일 수 있겠다 와 같은 

판단이 자연스럽게 떠오를 수 있도록 발전하는것이 알고리즘 공부를 하는 이유인 것이다.