자료구조의 빅오 표현법, binsearch() 알고리즘을 C언로 표기하고 시간복잡도 어떻게 되는지에 대한 설명
- 최초 등록일
- 2010.04.11
- 최종 저작일
- 2010.04
- 6페이지/
한컴오피스
- 가격 1,000원
![할인쿠폰받기](/images/v4/document/ico_det_coupon.gif)
소개글
자료구조와 C라는 책에
53페이지 연습문제 20번에 대한 풀이
binsearch() 알고리즘을 C언로 표기하고 시간복잡도 어떻게 되는지에 대한 설명입니다.
목차
교재 53페이지에 있는 연습문제 20번에 대해
(1) 각 함수의 실행시간을 big-oh 표기법으로 나타내어라.
(2) 실제로 프로그램을 실행시켜서 (1)의 결과와 비교한 다음결과를 워드 프로세서를 사용하여 보고서로 만든다. 실행 단계수는 count 변수를 사용한다.
교재 36페이지에 있는 binsearch() 알고리즘을 C 언어로 구현해 보라.
본문내용
교재 53페이지에 있는 연습문제 20번에 대해
(1) 각 함수의 실행시간을 big-oh 표기법으로 나타내어라.
- ex1
int a; ->실행빈도수 1
int i; ->실행빈도수 1
for (i=0; i<n; i++) ->실행빈도수 n+1
a=1; ->실행빈도수 n
→ 프로그램 실행 시간을 계산하면 2n+3가 되고 f(n) = 0(n)이다.
f(n) = 2n+3≤a*n , n≥b a=4, b=2일 때 n≥2에 대하여 2n+3≤4n이 되기 때문이다.
그래서 0(n)이다.
교재 36페이지에 있는 binsearch() 알고리즘을 C 언어로 구현해 보라.
배열 a[]는 65,536개의 데이터를 저장할 수 있도록 선언하고,
1부터 65,536까지의 정수값을 순서대로 저장하라.
임의로 선택한 10개의 탐색 키에 대해 비교 횟수가 얼마나 되는 측정해 보고,
시간 복잡도가 O(log n)이 되는지 확인해 보라.
여기서 log는 2를 밑으로 하는 로그 함수이다. 따라서 log 65,536 = 16 이다.
- 코드
#include <stdio.h>
static int count=0;
int Bin(int a[], int key, int left, int right)
{
int mid;
count++;
참고 자료
없음