def bubblesort(x, n): for last in range(n, 1, -1): #check sorting changed = False for i in range(0, last-1, 1): if x[i]>x[i+1]: temp = x[i+1] x[i+1] = x[i] x[i] = temp changed = True if changed == False: return x return x 1. 선택 정렬 (Selection Sort) selectionSort(A[], n) { for last=0 and choosen

1. 점화식의 점근적 분석 방법 1) 반복대치 우선 병합정렬의 알고리즘은 아래와 같다. Merge sort의 전체 걸리는 시간을 T(n)이라고 하면 3,4번째줄은 각각 절반을 merge sort하는 것임으로 T(n/2)가 걸리게 된다. 그리고 5번째 줄은 3,4에서 구한 값을 합치는 것인데 이를 정렬이 될때까지 반복하면 최대 5번째 줄을 n-1번 반복하게 된다.(n개가 역순으로 되어있을때) 즉 걸리는 시간을 다 합치면 을 얻을 수 있다.여기서 점근적 복잡도의 계산을 용이하기 하게 위해 주로 라고 둔다. 은 항상 만족하고 이므로 이여서 알고리즘 분석에 영향을 주지 않는다. 이를 이용하여 위의 Mergesort를 분석해보자. 임고 여기서 라고 해보자. 그러면가되면서 마지막줄이 가된다. 따라서 를 얻을 수 있..

1. O-표기법 정의 : 모든 에 대하여 인 양의 상수 c와 n0가 존재한다라는 뜻이다. 즉 상한선의 뜻을 지닌다. 예를들어보면 이다. 이를 증명해보면 에서 이므로 모든 양수 n_0에서 가능함으로 이다. 2. Ω-표기법 정의 : 모든 에 대하여 인 상수 c와 n_0가 존재한다는 뜻이다. 즉 하한선을 의미한다. 예를 들어보면 이다. 이를 증명해보면 우선 c를 1로 잡아본다. 그러면 이고 이는 어차피 양의 n에서 다 만족한다. 3. Θ-표기법 정의 : 충분히 큰 모든 n에 대하여 를 만족하는 가 존재한다는 뜻이다. 즉 점근적으로 같은 기울기를 가지고 있으면 된다. 따라서 이를 아래와 같이 정의하기도 한다. 4. o-표기법(리틀 오) 정의 : 즉 빅 O와 다르게 g(n)이 f(n)을 압도한다. 예를들어 는 옳..