'공부/알고리즘'에 해당되는 글 13건

  1. 2011.06.28 4 Recursion
  2. 2011.06.24 3장 Growth of Funtions
  3. 2011.06.23 2장 insertion sort, merge sort, binary search, selection sort, bubble sort 1
공부/알고리즘2011. 6. 28. 21:59


순환문제

문제푸는 방법
1. substitution method
결론을 가정하고 수학적귀납법을 써서 가정이 참임을 보이는 것.
2. Recursion-tree method
3. Master method

 

'공부 > 알고리즘' 카테고리의 다른 글

8장 Sorting in Linear Time  (0) 2011.07.03
7장 Quicksort  (0) 2011.07.03
Heapsort  (1) 2011.06.30
3장 Growth of Funtions  (0) 2011.06.24
2장 insertion sort, merge sort, binary search, selection sort, bubble sort  (1) 2011.06.23


Posted by skyjumps
공부/알고리즘2011. 6. 24. 21:13


O-notation
Upper bound. 이보다 커질 수 없다.

Ω-notation
lower bound. 이보다 작아질 수 없다.

Θ-notation
tight bound. upper bound도 될 수 있고 lower bound도 될 수 있다.




ο-notation (small O notation)
tight 하지 않은 upper bound

ω-notation (small Ω notation)
tight 하지 않은 lower bound

함수의 비교
 

Θ,Ω,ο,ω 를 관계로 보면
Transitivity
aRb and bRc -> aRc

Reflexivity
aRa

Symmetry
aRb -> bRa

Transpose symmetry 
aRb -> bR'a

'공부 > 알고리즘' 카테고리의 다른 글

8장 Sorting in Linear Time  (0) 2011.07.03
7장 Quicksort  (0) 2011.07.03
Heapsort  (1) 2011.06.30
4 Recursion  (0) 2011.06.28
2장 insertion sort, merge sort, binary search, selection sort, bubble sort  (1) 2011.06.23


Posted by skyjumps
공부/알고리즘2011. 6. 23. 19:09


Insertion sort
 

Insertion sort란 정렬된 리스트에 정렬을 유지하도록 키를 삽입하는 정렬.
Performance
Running time
Instruction의 수를 센다.
Instruction에는 더하기 빼기 같은 산술계산과 Load, store, copy 같은 데이터 이동이나 if나 함수호출 등과 같은 Control이 있다.
running time은 input의 갯수에 따라 달라진다.
for나 while loop은 loop body 보다 한번 더 실행된다. 조건 연산때문에
이미 많은 부분이 정렬되어 있을 때 사용하면 성능이 좋다.

Best case : 이미 정렬되어 있을때, 두번째 루프 안돌아도 되므로 수행시간은 an+b, 즉 linear function이다.
Worst case : 반대로 정렬되어 있을 때. quadratic function. O(n^2)

Space consumption : O(n)

Sorted in place : 내부에서 정렬이 된다.


Merge sort
 

두개의 정렬된 리스트를 하나의 정렬된 리스트로 만드는 것
이동의 수 : n1+n2
비교연산의 수 : <= n1+n2
따라서 O(n1+n2)

Divide : n개의 keys를 n/2인 두개의 리스트로 나눈다.
Conquer : 두개의 리스트를 재귀적으로 정렬한다.
combine : 두개의 리스트를 합친다. 

Running time
Divide : O(1), 중간 값만 계산하면 되니까.
Conquer : 2T(n/2), 리스트 2개가 재귀적으로 정렬하는 시간
combine : O(n)

Recursion tree


각 단계의 합 : cn
트리의 높이 : 2^k = n 으로부터 k = lgn, 따라서 높이 h = lgn+1
n이 1이 될때까지 2를 나눈 횟수+1이 높이. n(1/2)^k = 1,  k=lgn.

Binary search
 

T(n) = T(n/2) + 1
Running time이 1부터 ln n까지

Selection sort
 

리스트에서 가장 작은 숫자를 찾는 과정이 반복되는 정렬
자료 이동 횟수는 고정 3(n-1). 3은 최소값이 i번째 값과 바뀔 때(i는 첫번째 루프단계, 0부터 n-2까지). 총 n-1번 돈다.
같은 값이 있는 경우 상대적인 위치 변경 가능성이 있다. 

Bubble sort
 

바로 다음 값과 연쇄적으로 비교하면서 큰값이 마지막에 위치하도록 하는 정렬.
비교횟수 : Worst, Average, Best 가 일정.
이동횟수 : 자료가 역순으로 되어 있을때 Worst, 정렬되어 있을때 Best
 

'공부 > 알고리즘' 카테고리의 다른 글

8장 Sorting in Linear Time  (0) 2011.07.03
7장 Quicksort  (0) 2011.07.03
Heapsort  (1) 2011.06.30
4 Recursion  (0) 2011.06.28
3장 Growth of Funtions  (0) 2011.06.24


Posted by skyjumps