Algorithms: Efficiency, Analysis, and Order

An algorithm is a step-by-step procedure used to solve a problem.

 

-------

 

The Importance of Developing Efficient Algorithms

 

Sequential Search

• array의 첫번째부터, item을 찾을 때까지 쭉 각각의  value를 살펴보는 방식

Binary Search

• array의 middle 포인트를 잡아서 찾는 item의 위치에 따라 반을 버려가면서 찾음(정렬 필수)

 

Sequential Search vs Binary Search

• n번의 탐색을 하는 sequential search보다, 조사할 array를 반으로 줄여주는 binary search가 더 효율적이다.
• O(n) vs O(logn) ==> O(logn)이 효율적

 

The Fibonacci Seqeunce

• def : fib(n) = fib(n-1) + fib(n-2) for n > 2; fib(1) = fib(2) = 1

• Sol 1. recursion

=> fib(5) = fib(4)+fib(3)

=> fib(4) = fib(3)+fib(2)   

=> fib(3) = fib(2)+fib(1)

===> 각 recursion에서 계산이 중복되게 발생한다 => 2^n/2 이상의 시간이 걸림 

 

• So1 2. bottom-up iteration

=> fib(0) = 1, fib(1) = 1, fib(2) = fib(0)+fib(1) = 2 ...... 

==> O(n) , linear time 

 

• design(접근 방식), approach(전략) 존재할 때, Which is better? ==> 수학,과학 analysis 필요
• So, sol 2 is better, Why? 시간복잡도가 더 작다.

 

Comparison

• search : sequential(iteration) vs binary(divide & conquer) ==> D&C better
• fibo : iteration vs recursion(D&C) ==> iteration better

• ==> 문제에 따라 접근, 설계하는 알고리즘은 다를 수 있다.

 

Analysis of Algorithms

• Algorithm analysis measures the efficiency of an algorithm as the input size becomes large
• 입력 크기가 커짐에 따라 알고리즘 효용성 측정

Complexity Analysis

• algorithm의 efficiency를 time에 관점에서 따질 때, 실제 CPU cycle의 개수 같은건 따지지 않음
• => algorithm이 돌아가는 computer에 의존하기 때문에
• 따라서 algorithm의 efficiency를 측정할 때는 input size에 따른 number of time some basic operation 을 따짐.
• ==> Time complexity analysis : basic operation이 얼마나 많이 돌아갔냐

Time complexity analysis

• T(n) : every case time complexity of algorithm
• W(n) : worst-case
• A(n) : average-case
• B(n) : best-case

 

Order

• n.. 5n... 1000n.. ==> linear time algorithm ( n: input size )
• n^2.. 0.01n^2... ==> quadratic time algorithm
• 당연히 linear time 이 훨씬 efficient 하다.

 

An Intuitive Introduction to Order

• order == 그 문제를 풀기 위해 수행되는 basic operation의 개수를 모두 헤아린 것.
• basic operation? : dependency가 없는 이론적 명령

• ex) 1n^2+n+100 => complete quatratic function
• 위의 함수를 Θ(n^2)로 함축 => quadratic-time algorithm
• ==> 정확한 TC(time complexity)를 결정짓기 힘들기 때문에 이렇게 한다...

Time Complexity analysis

1. determine input size(n)2. choose the BOs3. determine how many times BOs are done.

 

 

A Rigorous Introduction to Order

• Big O ==> asymptotic behavior 
• Big O 란.. basic operation에 따른 T() function의 asymptotic(점근적) upper bound 이다.
• ==> 아무리 오래걸려도, 적어도 이만큼이다. 하는 보장의 느낌의 TC
• ==> worst case time complexity 가 중요.
• 우리 수업에서의 T(n) = W(n)

 

 

궁극적인 목표 == Large-scale 문제를 만났을 때, linear time algorithm을 만드는 것.