2025/10/09 TIL

김기훈·2025년 10월 9일

목록 보기

34/194

Big-O(빅-오) ⇒ 상한 점근
- 시간복잡도: 최악
  - 최악의 경우를 고려하여 대비하기 위해 사용 (가장 많이 사용)
  - 입력값의 변화에 따라 연산을 진행할 때, 연산 횟수에 비해 시간이 얼마만큼 걸리는가? 를 표기하는 방법
Big-Ω(빅-오메가) ⇒ 하한 점근
- 시간복잡도: 최선
  - 최선의 경우만 고려하기 때문에 문제 발생시에 어디에서 문제가 발생했는데 알아내기 위한 많은 시간이 필요
Big-θ(빅-세타) ⇒ 그 둘의 평균
- 시간복잡도: 중간(평균)
  - 평균적으로 생각했을때 걸리는 시간에 최악의 경우가 몇번 발생하여 시간이 오래걸리면 최선과 비슷한 문제 발생

O(1): 일정한 복잡도(constant complexity)
- 입력값이 증가하더라도 시간이 늘어나지 않는다.
  - 입력값의 크기와 관계없이, 즉시 출력값을 얻어낼 수 있다는 의미
O(n): 선형 복잡도(linear complexity)
- 입력값이 증가함에 따라 시간 또한 같은 비율로 증가하는 것을 의미
  - 입력값이 1일 경우에 1초가 걸린다면 입력값이 100인경우에는 100초가 걸리는 경우를 말함
O(log n): 로그 복잡도(logarithmic complexity), Big-O표기법중 O(1) 다음으로 빠른 시간 복잡도
- 매번 숫자를 제시할때마다 경우의 수가 절반으로 줄어듬
  - ex) 스무고개 숫자찾기 게임
  - 1~100 중 30을 고름 , 50선택 down , 25선택 up 이런식으로 절반씩 줄이는 것
O(n2): 2차 복잡도(quadratic complexity)
- 입력값이 증가함에 따라 시간이 n의 제곱수의 비율로 증가하는 것
  - 입력값이 1일 경우 1초 , 입력값이 5일 경우 25초 걸리게 되는 경우 시간복잡도는 O(n2)
O(2n): 기하급수적 복잡도(exponential complexity), Big-O 표기법 중 가장 느린 시간 복잡도
- 구현한 알고리즘의 시간 복잡도가 O(2n)이라면 다른 접근 방식을 고민해 보는 것이 좋음
  - ex) 재귀함수 피보나치 수열

안녕하세요.

TIL