[매일매일] 백엔드 기술 일기: 시간 복잡도와 공간 복잡도의 차이, 그리고 빅오(Big-O) 표기법 완전 정리

알고리즘을 선택하거나 성능을 분석할 때 가장 많이 듣는 말이 바로 시간 복잡도와 공간 복잡도입니다. 또한 이를 표현하는 방법으로는 흔히 빅오(Big-O) 표기법을 사용합니다. 이번 글에서는 이 세 가지 개념을 쉽게 이해할 수 있도록 정리했습니다.

출처 및 참고https://velog.io/@welloff_jj/Complexity-and-Big-O-notation

복잡도(Complexity): 시간 복잡도와 공간 복잡도, 그리고 빅오(Big-O) 표기법 시간 복잡도와 공간 복잡도, 그리고 빅오 표기법 velog.io

🕒 시간 복잡도(Time Complexity)시간 복잡도란?

알고리즘이 실행될 때, 입력 크기 nnn에 따라 연산을 몇 번 수행하는지를 수치화한 것.

예를 들어, 배열의 모든 요소를 한 번씩 순회해야 하는 경우라면 입력 크기에 비례하여 연산이 늘어나므로 O(n)이라고 표현합니다.왜 필요한가요?실행 시간을 실제로 재면, 기계 성능이나 현재 상태에 따라 다르게 나옵니다. 그래서 더 일반화된 기준으로 연산량을 계산해 속도를 비교하는 것이 좋습니다.예를 들어, 두 알고리즘이 둘 다 1초 이내에 끝난다고 해도, 입력이 커질수록 성능 차이가 크게 벌어질 수 있기 때문에 시간 복잡도를 분석합니다.

💾 공간 복잡도(Space Complexity)공간 복잡도란?

알고리즘이 실행될 때 필요한 메모리 사용량을 입력 크기 nnn에 따라 표현한 것.

예를 들어, 입력 배열 외에 새로운 배열을 하나 더 만들어야 하는 알고리즘이라면 메모리가 추가로 필요하고, 이 메모리 사용량이 얼마나 늘어나는지 표현합니다.즉, 시간은 빠르지만 메모리를 많이 쓰는지, 메모리를 적게 쓰지만 느린지 등 트레이드오프를 고려할 수 있습니다.

🔍 빅오(Big-O) 표기법시간과 공간 복잡도를 표현할 때 가장 널리 쓰이는 것이 바로 빅오 표기법입니다.

입력 크기 nnn이 커질수록 알고리즘의 실행 시간 또는 메모리 사용량이 어떻게 변하는지를 나타내는 점근적 표기법입니다.

✨ 특징계수는 무시: 5n5n5n, 100n100n100n처럼 상수배는 무시합니다. → O(n)가장 큰 항만 남김: n2+n+1n^2 + n + 1n2+n+1이라면 → O(n²)

📑 빅오 표기법 예시

코드

빅오

for (int i = 0; i < n; i++)

O(n)

for (int i = 0; i < n; i++) for (int j = 0; j < n; j++)

O(n²)

for (int i = 0; i < n; i++)for (int i = 0; i < m; i++)

O(n + m)

for (int i = 0; i < n * k; i++)

O(n) (상수 k는 무시)

// n이 입력되면 n번 루프가 반복되므로, O(n)으로 표기합니다. for (int i = 0; i < n; i++) { … }

// 아래 루프는 O(n)으로 표기합니다. n이 무한에 가까울 수록 k가 의미가 없기 때문입니다. (상수항과 계수 무시) int k = 5; for (int i = 0; i < n * k; i++) { … }

// 입력값인 n과 m이 독립적이라면 빅오는 더할 수 있습니다. O(n + m)으로 표기합니다. for (int i = 0; i < n; i++) { … } for (int i = 0; i < m; i++) { … }

// 빅오는 곱해질 수 있습니다. O(n^2)으로 표기합니다. for (int i = 0; i < n; i++) { for (int j = 0; j < n * 5; j++) {} }

// 가장 큰 항 외에는 무시할 수 있습니다. O(n^2)로 표기합니다. for (int i = 0; i < n; i++) {}

for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) {} }

🧰 추천 학습 자료✅ [10분 테코톡] 🙋‍♂️ 제이의 시간복잡도 — 유튜브https://www.youtube.com/watch?v=IEH3YA2Nn4Q

✅ Eleanor Lim님 유튜브 — 빅오(Big-O) 표기법 완전정복https://www.youtube.com/watch?v=6Iq5iMCVsXA

✅ 노마드 코더 — 개발자라면 이제는 알아야 하는 Big-O 설명해드림 (10분컷)https://www.youtube.com/watch?v=BEVnxbxBqi8

🔗 마무리시간 복잡도와 공간 복잡도는 알고리즘을 평가하는 두 가지 축입니다. 둘 다 적절히 고려하여 효율적인 코드를 작성하는 것이 중요합니다. 그리고 이를 표현하는 빅오 표기법은 개발자라면 꼭 알아야 할 기본기이니, 위 자료를 참고해 복습해보시길 추천합니다. 🙌

​