[고2 자료구조] 2학기 2차

빅오 표기법

1. O(1) 자료 수와 상관없이 일정한 수행 시간을 가진다.
2. O(n) 자료 수의 증가가 수행 시간과 일정하게 늘어난다.
3. O(n²) 자료 수가 2배로 늘어나면 수행 시간은 4배로 늘어난다.

 

	시간 복잡도	알고리즘	순서도랑 프로그램도 나오는데 포기해라 애송이 우린 다 죽고 말거야 이히히
선택 정렬	O(n²)	1. 현재 자료 중에서 가장 작은 값을 찾는다. 2. 그 값을 맨 앞에 위치한 기준 값과 교체한다. 3. 교체한 기준 값을 제외한 나머지 자료에 대하여 위의 과정을 반복한다.
버블 정렬		1. 첫 번째 값과 두 번째 값을 비교하여 작은 값을 앞에 놓은 후     두 번째 값과 세 번째 값을 비교하여 작은 값을 다시 앞에 놓는 과정을 반복한다. 2. n-1번째와 n번째 값까지 교환하여     n번째 값이 가장 큰 값을 가지면 1단계가 종료된다. 3. n번째 값을 제외하고 첫 번째에서 n-1번째의 값을 위와 같은 방법으로 반복하면     n-1번째에 두 번째로 큰 값이 위치하게 된다.   4. n-1회 반복하면 정렬이 완료된다.
선택 정렬		1. 현재까지 정렬된 부분의 마지막 값과 삽입하고자 하는 값을 비교한다. 2. 삽입하고자 하는 값이 더 작으면     이미 정렬된 값을 한 칸 뒤로 이동하여 빈 공간을 만든다. 3. 삽입하고자 하는 값이 더 클 때까지 2번을 반복 수행한다. 4. 삽입하고자 하는 값이 더 크면 빈 공간에 값을 추가한다. 5. 위의 과정을 n-1번 수행하면 정렬이 완료된다.