Ch1.3 Analysis of Algorithms

Analysis of Algorithms

• 알고리즘을 분석

 

"Complexity" of an Algorithm

Complexity = Efficiency

 

The input size

• could be the size of array
• could be a single number
• For graphs, both the number of vertices and the number of edges are the input size

The basic operation

• The total work done by the algorithm is roughly proportional to the number of times Op is executed

 

Time Complexity Analysis

how many times the basic operation is done for each value of the input size

 

 

 

Best case analysis - 1

Worst case analysis - N

 

Average Case Analysis

 

 

 

 

1.4 Order

Complexity Function

• Any function form the non-negative integer to the non-negative real numbers

 

 

 

 

Big O 

 

 

1. n^2 + 10n ∈ O(n^2) ?

Proof 1 

We know that n >= 10, n^2  >=  10n

 

Another Proof 2

We know that n >= 1, 10n^2 >= 10n

 

2. 5n^2 ∈ O(n^2) ?

Proof 

n >= 0, n^2 >= n^2

 

 

 

3. n(n+1) / 2 ∈ O(n^2) ?

Proof For n >= 0, n >= n-1

 

 

4. n ∈ O(n^2) ?

 

 

 

 

5. n^2 ∈ O(n^2 + 10n) ?

 

 

 

6. n^3 ∈ O(n^2) ? No

 

 

Omega O

 

 

Theta

 

 

 

 

 

Small O / Little O

 

 

 

 

 

 

 

참고문헌

 

Richard Neapolitan, 「Foundations Of Algorithms」

Thomas H. Cormen et al., 「Introduction to Algorithms」

https://sdolnote.tistory.com/entry/BigOLittleo

Big O표기법과 little o표기법에 대한 설명

https://ko.khanacademy.org/computing/computer-science/algorithms/asymptotic-notation/e/quiz--asymptotic-notation

 

---

⊙ 이 글은 개인 공부를 목적으로 작성된 글입니다.

⊙ 내용에 대한 오류나 피드백 감사히 받고 있습니다 !