1. 복잡도 - 자바로 구현하고 배우는 자료구조

레퍼런스는 네이버 edwith - 자바로 구현하고 배우는 자료구조 입니다.

 

복잡도

---

Complexity 개념

• 인풋 ≥ 0
• functions do more work for more input
• drop all constants
• ignore lower order terms
• ignore the base of logs
• 2n = O(n) → 2n 이 O(n)의 집합에 속한다는 뜻

빅오 표기법

O (빅오): same or faster

o (리를오)

세타 : Same rate

빅 오메가 : Same or slower

리를 오메가 : slower

빅오 표기법 예제

n^4/3 은 O(n logn)이 될수 없다.

3n^3 + …. = 세타 (n^3)이 된다.