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

목차

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

본문내용

알고리즘 복잡도를 표기하는 방법은 크게 빅-오, 빅-오메가, 세타 세 가지 표기법이 있다. 이 표기법들은 입력 크기에 따른 알고리즘의 실행 시간 또는 공간 요구사항을 기술하는 방법이다.
빅-오 표기법(Big O notation)은 알고리즘의 최악의 경우 복잡도를 나타낸다. 즉, 알고리즘에 주어진 입력의 크기가 커짐에 따라 실행 시간이 어떻게 증가하는지를 상한선으로 보여준다. 예를 들어, 알고리즘이 O(n2)으로 표기된다면, 최악의 경우 입력 크기에 따른 실행 시간이 제곱에 비례하게 증가한다는 것을 의미한다. 빅-오메가 표기법(Big Omega notation)은 알고리즘의 최선의 경우 복잡도를 나타낸다. 즉, 알고리즘에 주어진 입력의 크기가 커짐에 따라 실행 시간이 어떻게 증가하는지를 하한선으로 보여준다. 예를 들어, 알고리즘이 Ω(n)으로 표기된다면, 최선의 경우 입력 크기에 따른 실행 시간이 선형적으로 증가한다는 것을 의미한다.

참고자료

· Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein, 2009, Introduction to Algorithms, 3rd Edition