다음은 알고리즘의 복잡도 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)의 증가율을 위에서 제한한다.
- Ω: 을 요구하는 하한 정의로 부등호 방향이 반대다.
- Θ: 처럼 위아래를 모두 감싸야 하므로 상한 조건만으로는 성립하지 않는다.
- Γ: 알고리즘의 점근 표기로 쓰이지 않는 기호다.
오류나 개정된 내용이 보이면 알려주세요
이어서 풀어보기
[7급 국가직 자료구조론] 10년 1회차 20문항 이어서 보기문제·정답·해설을 한 페이지에서 이어서 볼 수 있어요비슷한 기출
- 다음은무엇에관한정의인가? <imgsrc= {"answer":2,"content":[{"content":"직업","url":""},{"con[직업상담사 2급 필기] 19년 1회차
- 괄호()안에알맞는단어를쓰시오. 디자인패턴중에서()패턴은반복적으로사용되는객체들의상호작용을패턴화한것으로,클래스나객체들이상호작용하는방법이다.알고리즘의패턴에는inter2021년 정보처리기사실기 2회차
- 시스템에저장되는패스워드들은hash또는암호화알고리즘의결과값으로저장된다.이때암호공격을막기위해똑같은패스워드들이다른암호값으로저장되도록추가되는값을의미하는것은?21년-3회차-정보처리기사-필기