Big O notation

복잡도에 가장 영향을 많이 끼치는 항의 상수인자를 빼고 나머지항을 없애서복잡도를나타내는표기법!

상수시간 시간 복잡도 O(1)

 : 입력 크기와 상관없이 일정한 시간 복잡도를 가지는 것

  (e.g. : 입력과 출력, 곱하기, 간단한 비교if문, 배열의 인덱스)

#include<iostream>
using namespace std;
int N, cnt;
void Func(int N) {
	cnt++;
	cout << cnt << '\n';
	if (N == 0) return;
	for (int i = 0; i < 3; i++) {
		Func(N - 1);
	}
	return;
}
int main() {
	cin >> N;
	Func(N);
	return 0;
}

이 함수의 시간복잡도를 점화식으로~

 

N=1일때 cnt = 4(1+3^1)

N=2일때 cnt = 13 (+9 =1+ 3^2)

N=3일때 cnt = 40(+27= 3^3)

N=4일때 cnt = 121(+81 = 3^4)

.

.

.

즉 등비수열의 합이다~

그러므로.. 가장 주요한 영향을 주는 3^n을 빼고 나머지를 제외

즉 이 코드의 시간 복잡도는 = 3^n

 

시간 복잡도는 왜 중요할까?

시간복잡도를 O(n^2)을 O(n)으로 줄인다는 건 4초였던 코드를 2초로 또는 9초였던 코드를 3초로 개선했다는 의미!

 

어떨 때 시간복잡도를 고려해야할까?

OPENAI 왈

 

시간복잡도를 고려해야 하는 상황

1. 대규모 데이터 처리

• 데이터 크기가 매우 클 때 시간복잡도는 핵심적인 요소입니다.
  • 예: 대규모 데이터셋에서 검색, 정렬, 필터링 등.
  • 효율이 낮은 알고리즘은 실행 시간이 급격히 증가합니다.
• 예:
  • 데이터 분석에서 10억 개 이상의 데이터를 처리해야 하는 경우.
  • 게임 개발에서 수천 개의 오브젝트 충돌 처리.

2. 실시간 시스템

• 실시간 반응이 필요한 시스템은 시간복잡도를 신경 써야 합니다.
  • 예: 게임 개발, 금융 거래 시스템, IoT 제어 시스템 등.
  • 한 프레임 내에서 특정 알고리즘이 수행될 수 있도록 최적화해야 합니다.
• 예:
  • 게임에서 AI 경로 탐색(A*)이 16ms(60FPS) 안에 끝나야 함.
  • UI 업데이트가 부드럽게 이루어지기 위해 O(n) 이하의 복잡도를 유지해야 함.

3. 대규모 사용자 또는 트래픽 처리

• 웹 서버, 모바일 앱 등에서 다수의 사용자 요청을 처리해야 할 때, 비효율적인 알고리즘은 성능 병목을 초래합니다.
  • 예: 검색 기능에서 O(n²) 알고리즘 사용 시, 사용자 수 증가에 따라 검색 속도가 급격히 느려짐.
• 적절한 예:
  • 데이터베이스 쿼리 최적화.
  • API 서버의 요청 처리 알고리즘 개선.

4. 정확한 응답 시간이 중요한 작업

• 예측 가능한 시간 내에 결과를 제공해야 하는 경우.
  • 예: 경로 탐색, 최적화 문제, 실시간 스트리밍 처리.
  • 시간복잡도가 높은 알고리즘은 예측 불가능한 성능을 유발할 수 있음.

5. 임베디드 시스템 및 제한된 리소스

• 메모리나 CPU 성능이 제한된 환경에서는 효율적인 알고리즘 선택이 필수입니다.
  • 예: IoT 디바이스, 스마트폰, 마이크로컨트롤러.
• 저사양 장비에서도 적정 성능을 유지해야 하므로 시간복잡도뿐 아니라 공간복잡도도 고려해야 합니다.