알고리즘) 알고리즘 복잡도 표현법을 설명하고, Bubble Sort(버블 정렬), Insertion Sort(삽입 정렬)의 정렬 성능을 빅오(Big-O) 표현법으로 나타내시오

소개글

알고리즘) 알고리즘 복잡도 표현법을 설명하고, Bubble Sort(버블 정렬), Insertion Sort(삽입 정렬)의 정렬 성능을 빅오(Big-O) 표현법으로 나타내시오에 대한 보고서 자료입니다.

목차

목차
1. 알고리즘의 복잡도 표기법으로 빅-오메가 표기법, 세타(Theta) 표기법, 빅-오 표기법을 설명하시오.
2. 버블 정렬 알고리즘의 동작 과정을 설명하시오.
3. 삽입 정렬 알고리즘의 동작 과정을 설명하시오.
4. 버블 정렬과 삽입 정렬 알고리즘을 빅-오 표현법으로 나타내시오.
5. 출처 및 참고문헌

본문내용

왜냐하면 이는 정렬을 수행하는 동안 상수 개의 공간만을 필요로 하기 때문이다.
삽입 정렬의 최선의 경우는 이미 정렬된 리스트를 정렬하는 경우이다. 이 경우 각 원소를 한 번씩만 확인하므로 시간 복잡도는 O(n)이 된다. 하지만 최악의 경우(역순으로 정렬된 리스트)와 평균적인 경우에는 각 원소가 이미 정렬된 부분에 삽입될 위치를 찾기 위해 모든 이전 원소들을 확인해야 하므로 시간 복잡도는 O(n2)가 된다. 공간 복잡도는 O(1)이다, 왜냐하면 추가적인 저장 공간 없이 입력 리스트 내에서 정렬이 수행되기 때문이다. 즉, 두 알고리즘이 모두 최악의 경우와 평균적인 경우에는 O(n2)의 시간 복잡도를 가지지만, 삽입 정렬은 이미 정렬된 경우에는 O(n)의 시간 복잡도를 가지므로 약간 더 효율적이다. 이는 작은 크기의 데이터나 대체로 정렬이 되어 있는 데이터에 대해서는 삽입 정렬이 버블 정렬보다 선호되는 이유이다.
따라서, 두 알고리즘이 모두 최악의 경우와 평균적인 경우에는 O(n2)의 복잡도를 가지지만, 삽입 정렬은 이미 정렬된 배열에 대해서는 O(n)의 복잡도를 보인다. 이는 삽입 정렬이 일부 특정 상황에서는 더 효율적으로 동작할 수 있음을 의미한다 Thomas 외, 2009, Introduction to Algorithms, 3rd Edition, 36-37쪽 참고.
.
5. 출처 및 참고문헌
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein, 2009, Introduction to Algorithms, 3rd Edition

키워드

알고리즘,   복잡도,   표현법,   버블정렬,   삽입정렬,   빅오표현법