Big O에 대한 이해

1. 알고리즘 성능 분석의 필요성

1 - 1. 사용자 경험과 성능의 관계

1. 사용자는 시스템이 얼마나 빨리 반응하는지를 체감하며, 대기 시간이 길수록 이탈률이 높아진다. 따라서 응답속도는 사용자 만족도에 직결된다.
2. 따라서 성능이 느린 애플리케이션은 첫 방문 시 나쁜 인상을 주게 되고, 장기적으로 사용자의 반복 방문률에도 영향을 준다. 이는 커머스, 콘텐츠 플랫폼 등에서 고객 유지율과 직접 연결된다.
3. 모바일 네트워크 환경이나 성능이 낮은 디바이스에서는 알고리즘 효율성이 더 중요하다. 따라서 리소스가 제한된 환경에서는 효율적인 코드가  사용자 경험을 좌우한다.

1 - 2. 시스템 자원과 비용의 관계

1. 클라우드 기반 인프라에서는 자원 사용량이 곧 요금으로 이어진다.
2. CPU, 메모리, 네트워크 자원을 과도하게 사용하는 알고리즘은 성능 저하 뿐만 아니라 다른 서비스에도 영향을 줄 수 있다.
3. 반대로 효율적인 알고리즘은 같은 리소스로 더 많은 요청을 처리할 수 있게 해주며, 인프라의 규모를 줄이고 비용을 절감할 수 있다.

1 - 3. 실행 시간 측정의 문제점

1. 동일한 코드라도 실행하는 컴퓨터의 사양, 운영체제, 백그라운드 프로세스 등에 따라 실행 시간이 달라진다.
2. GC 발생 여부, 캐시 상태, CPU 부하 등과 같은 코드 외적 요소들이 성능 측정에 영향을 준다.
3. 실행 시간을 측정할 때는 여러 번 반복 실행하고 평균을 내야 비교적 신뢰할 수 있다.

1 - 4. 하드웨어 의존성 문제

1. 동일한 코드도 하드웨어 스펙에 따라 결과가 달라진다.
2. 알고리즘 자체의 성능보다 환경에 영향을 받는다.
3. 공유 자원을 사용하는 클라우드 환경에서는 측정 시점마다 리소스 사용량이 달라져 편차가 커진다.

2. Big O 표기법의 필요성

2 - 1. 하드웨어 독립적인 성능 비교

1. Big O 표기법은 입력 크기에 따른 연산 횟수 증가율에 초점을 맞춘다. 따라서 알고리즘 자체의 효율성을 비교할 수 있다.
2. 어떤 언어로 구현했는지, 어떤 OS애서 실행했는지와 관계없이 알고리즘의 Big O 표현은 동일하기에 다양한 환경에서도 일관된 기준 제공이 가능하다.
3. 시간 뿐만 아나라 메모리 사용량도 분석할 수 있어, 제한된 리소스 환경에서 중요한 의사결정의 기준이 된다.

2 - 2. 최악의 경우 분석의 중요성

1. 실제 서비스 환경에서는 예외적인 상황이나 이상 데이터가 자주 발생할 수 있다.
2. 최악의 경우에도 일정 수준의 성능이 보자오디어야 서비스 품질을 안정적으로 유지할 수 있다. 즉, 안정성과 신뢰성을 확보하기 위해 필요하다.
3. 최악의 경우를 분석하면 특정 알고리즘이 어떤 입력에서 문제를 일으킬 수 있는지 사전에 예측할 수 있다.

 

3. Big O 표기법의 이해

2 - 1. 수학적 의미

점근 표기법은 어떤 함수의 증가 양상을 다른 함수와의 비교로 표현하는 수론과 해석학의 방법으로, 알고리즘의 복잡도를 단순화할 때나 무한 급수의 뒷 부분을 간소화할 때 사용된다. Big O는 입력 크기(n)가 매우 클 때 알고리즘의 성능이 어떤 경향을 보이는지를 설명한다.

1. Big O는 정확한 연산 횟수가 아닌, 입력이 커질수록 연산이 얼마나 빠르게 증가하는지에 초점을 맞춘다. 이는 코드의 미래 확장성과 성능 예측에 유리하다.
2. Big O는 "이 정도보다 더 나쁘진 않다"는 의미의 상한선을 나타낸다.
3. O(n)은 입력이 두 배가 된면 연산도 두 배가 되고, O(n²)은 4배가 되는 것처럼 입력 증가에 따라 연산량에 변화가 생긴다.
4. 같은 기능을 수행하는 여러 알고리즘이 있을 때, 입력이 커질수록 어떤 알고리즘이 더 빠른지 판단하는 기준이 바로 증가율이다.
5. 처음에는 비슷해 보여도 입력이 커질수록 로그 기반 알고리즘과 제곱 기반 알고리즘의 성능 차이는 극적으로 벌어지므로, 시각적 그래프 자료를 활용해 이 차이를 비교해보면 효과적이다.
6. Big O에서 계수와 낮은 차수는 무시된다.

4. 주요 시간 복잡도

시간 복잡도란?

입력 크기(n)가 증가할 때, 알고리즘이 수행하는 연산의 횟수를 수학적으로 표현한 것으로, 주요 목적은 하드웨어나 언어에 상관없이 알고리즘의 성능 증가율을 비교하는 것이다. 시간 복잡도를 통해 입력이 커졌을 때 응답 시간이나 처리 시간의 변화 추이를 예측할 수 있으며, 일반적으로 Big O 표기법을 사용해 표현한다.

종류

• 상수 시간(O(1)) : 입력 크기(n)에 상관없이 항상 일정한 시간 내에 연산이 완료되는 경우. 연산 횟수가 고정되어 있어 가장 효율적이다.
• 로그 시간(O(log n)) : 입력을 반복적으로 나눠 매 연산마다 입력을 절반으로 줄이는 방식. 이진 탐색이 대표적이다.
• 선형 시간(O(n)) : 입력 데이터 전체를 한 번씩 순회하며 연산하는 경우로, 입력의 크기에 따라 연산 횟수도 그에 비례해서 증가한다.
• 선형 로그 시간(O(n log n)) : 데이터를 재귀적으로 반으로 나눈 뒤, 각 부분에 대해 n번 처리하는 알고리즘 구조에서 나타난다. 입력을 나누고, 각각에 대해 선형 연산을 수행하는 것으로 정렬 알고리즘 중 대부분의 효율적인 방식이 여기에 해당한다.
• 제곱 시간(O(n²)) : 각 요소마다 다른 모든 요소와 연산을 수행할 때 발생한다. 즉, n개의 데이터 각각에 대해 n번의 작업을 반복하는 구조라서 입력이 커질수록 처리 시간이 급격히 증가한다.

5. 공간 복잡도와 보조 공간

공간 복잡도란?

알고리즘이 작업을 수행하는 동안 사용하는 메모리의 양을 나타낸다. 입력 크기가 커짐에 따라 메모리 사용량이 얼마나 늘어나는지를 분석할 수 있다. 따라서 시간 복잡도와 달리 메모리 효율성에 중점을 둔다.

→입력 데이터 저장 공간 + 임시 작업 공간

 

보조 공간

입력 데이터를 제외하고, 알고리즘이 추가적으로 사용하는 공간. ex) 정렬을 위한 임시 배열