알고리즘 개념

cs50

 

1.Linear Search

왼쪽부터 오른쪽으로 하나하나씩 조회한다.

 

랜덤으로 되여있다.

o(n)

 

2. binary search

sord 되여있는 것을 

중간 중간 이런식으로 한다.

bi => two

divide conquer

o(log n)

 

big O -> O worst case

 

 

3. bubble sort

bubble sort 옆에 있는것과 비교하여 바꾼다.

 i , i+1

i 위치에 있는것 이 i+1 보다 크면 바꾼다.

O(n**2)

 

4. selection sort

한줄 보면서 제일  작은 것을 기억해서 처음과 잴 작은 것을 바꾼다.

0-> n-1

n(n-1)/ 2 => O(n**2)

 

5. insertion sort

 

 

6. recursion

left right 나누어서 한다. 

 

7. merge sort

left , rigth  따로 따로 하고 합친다.

7 4 5 2   6 3 8 1

4 7     

4 7 2 5

2 4 5 7 

 

6 3 8 1

3 6 1 8

1 3 6 8

 

2 4 5 7 1 3 6 8

 O( n log n )