170620(화) - Stanford Engineering's Algorithms (Asymptotic Analysis)

Stanford Engineering's Algorithms (Asymptotic Analysis)

Motivation

- Importance

Algorithms의 분석 및 design을 위한 vocabulary

- Sweet spot

algorithms에 대한 high-level reasoning을 위한 sweet spot 이다.

- architecture / language / compiler-dependent details 의 coarse(조잡함)를 충분히 suppress(억제) 한다.

- 서로 다른 algorithms 간에 분명한 useful comparisons 이 가능하다.

Asymptotic Analysis

- High-level idea

constant factors와 lower-order terms를 막는다.

constant factors : too System-dependent

lower-order terms : irrelevant for large inputs

- Ex

- Terminology

Running time is O(nlog n)

n = input size.

Big-Oh

- Definition

Usually, the worst-case running time of an algorithm

T(n), n = 1, 2, 3...

T(n) = O(f(n))

Basic Examples

Big Omega and Theta

Theta Notation

Little-Oh Notation

- Big O notation is less than or equal to type relation

- little O is strictly less than relation

- ex

T(n) = 2n

case Big oh

O(n), O(n^2)

case Little oh

O(n^2)

O(n)은 틀린표현