컴퓨터과학 CS50 2020 Lecture 3 : Algorithms

 

 

 

<강의 필기>

 

 

Linear Search

 

For i from 0 to n-1

  if number behind i’th door
    Return true
    
Return false

 

7개 문 뒤에는 숫자가 있다.
문 뒤에 있는 숫자 0 찾는 것을 어떻게 해야할까?
문 하나씩 다 열어보는 것이 방법일까?
여기서 숫자 0을 찾는 알고리즘은 무엇일까?

 

 

 

 

Binary search

 

If no doors
  Return False
  
If number behind middle door
  Return true
  
Else if number < middle door
  Search left half
  
Else if number > middle door
  Search right half

Binary search가 linear search보다 효율적이다.
보다 적은 메모리와 빠른 속도를 갖춘 알고리즘이다.
per seconds에 작업이 얼마나 처리되는 지는
CPU 속도 clock의 주파수 단위 hertz로 측정된다.

 

 

 

 

 

 

Algorithms

many errors를 해결하고 
success를 나타내는 변수를 출력한다.

error로 가는 방법은 다양한데
사람이 특정 상황에 서서히 적응해가는 모습으로 비유할 수 있다.

 

 

list of name에서 useful character는 무엇일까?
alphabetical order. ASCIIBetical order가 가능하다.
strcmp()는 각 string의 ASCIIBetical order에서 number가 어떻게 되는지 확인한다.

 

 

 

Comparison Sorting Algorithms
Randomize Array
Insertion Sort
Selection Sort
Bubble Sort
Quick Sort
Merge Sort
Shell Sort
Change Size

 

sorting은 
unsorted data를 입력하여 sorted data로 출력하는 과정이다.

 

 

 

 

 

 

Big O
contiouous block of memory는 grid 안에서 구조로 구성된다.
array는 주어진 시간(running)에 맞춰 작동한다.

 

Big Ordnung(the order of approximation)
efficency of algorithm를 나타내는 하나의 방법
running time of linear search을 측정한다.
input의 크기가 커질수록 시공간에 대한 요구사항을 나타내는 분류 알고리즘이다.

x label : size of problem
y label : time of solve

 

logarithmics algorithm : log n

linear algorithm : n

super linear algorithm : n log n

polynomial algorithm : n^c

exponential algorithm : c^n

 

 

Big O

The running time is at most.

O(1)

O(log n) binary search

O(n) linear search

O(n log n) merge sort, heap sort

O(n^c) strassen's matrix multiplication, insertion sort, bucket sort
O(n^2) selection sort, bubble sort

O(c^n) tower of hanoi

 

 

Omega

The running time is at least.

Ω(1) linear search, binary search

Ω(log n) 

Ω(n) bubble sort

Ω(n log n) merge sort
Ω(n^2) selection sort

Theta

The running time is on average.

Θ(1)

Θ(log n)

Θ(n)

Θ(n log n) : merge sort

Θ(n^2) : selection sort

 

 

 

Selection Sort
n + (n-1) + (n-2) + ... + 1 = n(n+1)/2
O(n^2) 

 

For I from 0 to n-1
  Find smalles item between i’th item and last item
  Swap smallest item with i’th item

63852741
13852746
12853746
12358746
12348756
12345786
12345687
12345678

 

 

Bubble Sort
n + (n-1) + (n-2) + ... + 1 = n(n+1)/2
O(n^2) 

 

Repeat untill sorted

  For I from 0 to n-2
  
    If i’th and I+1’th elemens out of order
      Swap them
      
  If no swaps
    Quit

 

1st
63852741
36852741
36582741
36528741
36527841
36527481
36527418

 

2nd
36527481
35627418
35267418
35264718
35264178

 

3rd
35264178
32564178
32546178
32541678

 

4th
32541678
23541678
23451678
23415678

 

5th
23415678
23145678

 

6th
23145678
21345678

 

7th
21345678
12345678

 

 

Merge Sort

If only one number
  Quit
  
Else
  Sort left half of numbers
  Sort right half of numbers
  Merge sorted halves

3568 1247
1568 3247
1268 3547
1238 6547
1234 6587
1234 5687
1234 5678

------------
6385 2741
36 85 2741
36 58 2741
35 68 2741
35 68 27 41
35 68 27 14
35 68 12 47
15 68 32 47
12 68 35 47
12 38 65 47
12 34 65 87
12 34 56 87
12 34 56 78

 

 

 

강의 자료

Week 3 - CS50

Tistory Eng

티스토리

 

 

 

 

 

CS50 Sandbox 

CS50 Sandbox

 

 

 

Comparison Sorting Algorithms

Comparison Sorting Visualization

 

 

 

Big O notation

Big O notation - Wikipedia

 

 

 

What is Big O Notation Explained: Space and Time Complexity

What is Big O Notation Explained: Space and Time Complexity

 

 

 

Analysis of Algorithms | Big-O analysis

Analysis of Algorithms | Big-O analysis - GeeksforGeeks

 

 

 

점근 표기법 (Asymtotic Notation) (Tistory Blog 시리시안)

[컴퓨터 공학] 점근 표기법 (Asymptotic Notation)