광운대 알고리즘 bubble sort, best case, worst case 등 시간복잡도 분석

소개

과제할때 참고하시면 좋을것 같습니다
bubble sort에 대한 best case, worst case 시간 복잡도 분석 레포트입니다
각각 case에 대한 증명, 실제 코드 돌렸을때 측정된 시간 그래프 등 작성했습니다.
과제 점수 모두 만점 받았습니다
코드와 레포트 모두 있습니다
(광운대 알고리즘 과제)

목차

1. For the following problems, consider the bubble sort whose input sequence has n distinct numbers and time complexity for the best case is O(n).
2. For the following cases of your pseudocode, find the number of comparisons of adjacent elements. Justify your answers mathematically. (a) The worst case (b) The best case
3. For the following cases of your pseudocode, find the running time in Θ-notation. Justify your answers mathematically. (a) The worst case (b) The average case
4. To show the results and graphs in Problems 5, 6, and 7, write your program with your comments. Explain your program at least four lines.
5. For the following cases of your program, show the step-by-step results. Explain the results at least four lines.
6. For the following cases of your program, draw the graphs for the number of comparisons of adjacent elements versus n. Explain the graphs at least four lines.
7. draw the graphs for the actual running time in your PC versus n. Write the basic information about the PC (e.g., CPU, RAM, OS). Explain the graphs at least four lines.

본문내용

For the following problems, consider the bubble sort whose input sequence has n distinct numbers and time complexity for the best case is O(n).
1. For the bubble sort, write your pseudocode with your comments.
for ( i=0; i < size - 1; i++) {
for ( j=0; j < size - (i+1); j++) { //뒤에 위치한 원소는 이미 정렬되었으므로 size - (i+1) 만큼 반복
end_count = 1;
if( arr[j] > arr[j+1] ) { //앞에 위치한 원소가 뒤에 보다 클 때 교환
end_count = 0;
switch data[j+1] and data[j];
} //비교하는 원소 중 가장 큰 수가 뒤로 가게 된다
}
If(end_count is 1) {return 0; } //정렬이 다 된 경우 바로 프로그램 종료
}

<중 략>

7. draw the graphs for the actual running time in your PC versus n. Write the basic information about the PC (e.g., CPU, RAM, OS). Explain the graphs at least four lines.
(a) The worst case
프로그램의 running time을 측정하기 위해 chrono 라이브러리를 사용했다. Chrono 라이브러리는 기존의 time 함수에 비해 정밀도가 높다. 프로그램의 running time을 측정 단위는 마이크로 초로 설정하고 측정했다. n은 100부터 100단위로 증가하도록 설정했다. n이 증가함에 따라 이전 값 과의 차이는 100부터 900까지 순서대로 약 40 / 70 / 100 / 140 / 190 / 220 / 360 / 630으로 증가폭이 n이 커질수록 점점 커지는 것을 알 수 있다.

참고자료

· 없음