[코딩 테스트 합격자 되기]1주차 - 3장 알고리즘 효율 분석

코딩 테스트 합격자 되기 1회독 스터디 내용입니다.

코딩테스트 합격자 되기 - 03 알고리즘의 효율 분석 : 네이버 카페 (naver.com)

3️⃣장 알고리즘 효율 분석

 

🧐시간복잡도란?

알고리즘의 성능을 나타내는 지표로, 입력 크기에 대한 연산 횟수의 상한을 의미함

시간 복잡도는 낮을수록 좋음

 

 

점근적 표기법

어떤 함수의 증가하는 추세를 표현하는 기법
(최악의 경우에 대하여 시간 복잡도를 표현하는 방법)

 

 

빅오 표기법

연산 횟수가 f(x) = 2x² + 3x + 5라면 시간 복잡도를 O( x² )과 같이 표기

 

 

---

✔️추가 문제

56P 테이블의 C*g(x) 제시 + 그래프

수식	빅오 표기	C	g(x)
3x² + 5x + 6	O(x²)	4	x²
x + logx	O(x)	1.5	x
2^{x} + 10x⁴ + 5x²	O( 2^{x} )	2	2^{x}
5x² - 6x	O(x²)	5	x²

 

 

다음을 만족하는 C가 있으면 f(x)의 최악의 시간 복잡도는 O(g(x)라고 씀

- 특정 x 시점 이후부터 항상 f(x) <= C * g(x)

- C는 상수

 

 

3x² + 5x + 6

• C * g(x) = 4x²

 

 

x + logx

• C * g(x)  = 1.5x
• 1보다 큰 상수값(정확히는 logx)이면 만족한다

 

 

 

2^{x} + 10x⁴ + 5x²

• C * g(x) = 50^{x}

 

 

5x² - 6x

• C * g(x) = 5x²