다음은 알고리즘의 복잡도 X를 위한 정의다. 어떤 복잡도에 대한 정의인… | [7급 국가직 자료구조론] 10년 1회차 기출문제 상세 페이지

1[7급 국가직 자료구조론] 10년 1회차
다음은 알고리즘의 복잡도 X를 위한 정의다. 어떤 복잡도에 대한 정의인가?
정의: f(n)=X(g(n))
모든 n (n≥n0)에 대해 f(n)≤cg(n)을 만족하는 두 양의 상수 c와 n0가 존재하면 f(n)=X(g(n))이다.
1
O (big oh)
2
Ω (omega)
3
Γ (gamma)
4
Θ (theta)
해설

정의된 X는 점근적 상한인 빅오(O) 표기이다.

충분히 큰 모든 n에서 f(n)이 cg(n) 이하라는 조건이므로 g(n)이 f(n)의 증가율을 위에서 제한한다.

  • Ω: f(n)≥cg(n)f(n)\ge cg(n)을 요구하는 하한 정의로 부등호 방향이 반대다.
  • Θ: c1g(n)≤f(n)≤c2g(n)c_1g(n)\le f(n)\le c_2g(n)처럼 위아래를 모두 감싸야 하므로 상한 조건만으로는 성립하지 않는다.
  • Γ: 알고리즘의 점근 표기로 쓰이지 않는 기호다.

오류나 개정된 내용이 보이면 알려주세요

이어서 풀어보기

[7급 국가직 자료구조론] 10년 1회차 20문항 이어서 보기문제·정답·해설을 한 페이지에서 이어서 볼 수 있어요7급 국가직 자료구조론 기출문제 암기장 전체 보기