Order(차수)

An Intuitive Introduction to Order

---

Below table shows that eventually the quadratic term dominates this function. That is, the values of the other terms eventually become insignificant compared with the values of the quadratic term. Therefore, although the function is not a pure quadratic function, we can classify it with the pure quadratic functions. This means that if some algorithm has this time complexity, we can call the algorithm a quadratic-time algorithm. Intuitively, it seems that we should always be able to throw away low-order terms when classifying complexity functions.

$n$	$0.1n^{2}$	$0.1n^{2} + n + 100$
10	10	120
20	40	160
50	250	400
100	1,000	1,200
1,000	100,000	101,100

 

👉 위의 표는 n 값이 커질수록 일차 항이나 상수 같은 다른 항의 값들은 이차 항의 값에 비하여 중요하지 않게 되며, 결국 이차 항이 이 함수를 지배한다는 사실을 보여준다.

이 말은 어떤 알고리즘이 이 시간복잡도를 가진다면 그 알고리즘을 이차 시간(quadratice-time)으로 분류할 수 있다는 의미이다. 직관적으로 복잡도 함수를 분류할 때는 낮은 차수의 항들은 항상 버릴 수 있어야 할 것처럼 보인다.

 

 

big O notation(빅 오 표기법)

---

For a given complexity function f(n), O(f(n)) is the set of complexity functions g(n) for which there exists some positive real constant c and some nonnegative integer N such that for all n ≥ N, g(n) ≤ c  × f(n).

 

Example We show that $5n^{2} \in \text{O}(n^{2})$.

Because, for $n ≥ 0$,
$5n^{2} ≤ 5n^{2}$ , 
we can take $c = 5$ and $N =0$ to obtain our desired result.

 

Example We show that $n^{2}+10n \in \text{O}(n^{2})$ .

Because, for $n ≥ 1$,

$n^{2} + 10n ≤ 2 × (n^{2})$

we can take $c = 2$ and $N = 10$ to obtain our desired result.

 

👉 주어진 복잡도 함수 f(n)에 대해서 g(n) ∈ O(f(n))이면 다음을 만족한다. 
어떤 양의 실수 c와 음이 아닌 정수 N이 존재할 때, 모든 n ≥ N에 대하여 g(n) ≤ c × f(n) 이 성립한다.

 

Meaning of g(n) ∈ O(f(n)) 

g(n) ∈ O(f(n)) 이면 g(n)은 f(n)의 big O라고 읽는다. big O는 x가 증가할수록 g(x)보다 항상 스케일이 큰 f(x)를 찾는 것이다. 이 표기법은 해당 알고리즘이 최악의 경우에도 어떤 성능을 보일지 가늠할 수 있어 시간복잡도 분석시 주로 사용된다.

 

 

• g(n): 어떤 알고리즘의 분석된 결과
• O(f(n)): f(n)의 비율로 증가하는 함수
• g(n)은 f(n)보다 빠르게 증가하지 않는다.
• an asymptotic upper bound: 점근적 상한

 

 

👉 어떤 함수 g(n)이 O($n^{2}$)에 속한다는 의미는, 함수 g(n)이 궁극적으로(=임의의 N보다 큰 값에 대해서는) 어떤 이차 함수 $c × n^{2}$보다는 작은 값을 가지게 된다는 것을 뜻한다. 따라서 g(n)은 어떤 이차 함수 $c × n^{2}$ 보다는 궁극적으로 좋다(=기울기가 낮다)고 할 수 있다.

어떤 알고리즘의 시간복잡도가 O(f(n))이라면, 입력크기 n에 대해서 이 알고리즘의 수행시간은 아무리 늦어도 f(n)은 된다는 뜻이다. 바꿔 말하면 이 알고리즘의 수행시간은 최악의 경우라도 f(n)과 같거나 이보다 작다는 의미이다. 즉, 이 알고리즘의 수행시간은 f(n)보다 더 느릴 수는 없다. (f(n)이 상한)

 

 

Omega notation(오메가 표기법)

---

For a given complexity function f(n), Ω(f(n)) is the set of complexity functions g(n) for which there exists some positive real constant c and some nonnegative integer N such that, for all n ≥ N, g(n) ≥ c × f(n).
​

Example We show that $n^{2} +10n \in \Omega(n^{2})$.

Because, for $n \ge 0$,

$n^{2} + 10n \ge n^{2}$,

we can take $c = 1$ and $N = 0$ to obtain our desired result.

 

Example We show that $n^{3} \in \Omega(n^{2})$.

Because, for $n \ge 1$,

$n^{3} \ge 1 × n^{2}$,

we can take $c = 1$ and $N = 1$ to obtain our desired result.

 

👉 주어진 복잡도 함수 f(n)에 대해서 g(n) ∈ Ω(f(n))이면 다음을 만족한다. 어떤 양의 실수 c와 음이 아닌 정수 N이 존재할 때, 모든 n ≥ N에 대하여 g(n) ≥ c × f(n)이 성립한다.

 

 

Meaning of g(n) ∈ Ω(f(n))

g(n) ∈ Ω(f(n)) 이면 g(n)은 f(n)의 Omega이다. Omega는 x가 증가할수록 g(x)보다 항상 스케일이 작은 f(x)를 찾는 것이다.

 

• g(n): 어떤 알고리즘의 분석된 결과
• Ω(f(n)): f(n)의 비율로 증가하는 함수
• g(n)은 f(n)보다 느리게 증가하지 않는다.
• an asymptotic lower bound: 점근적 하한

 

 

 

👉 어떤 함수 g(n)이 Ω(n2)에 속한다는 의미는, 함수 g(n)이 궁극적으로(=임의의 N보다 큰 값에 대해서는) 어떤 이차 함수 c × $n^{2}$보다는 큰 값을 가지게 된다는 것을 뜻한다. 따라서 함수 g(n)은 어떤 이차 함수 c × $n^{2}$보다는 궁극적으로 나쁘다(=기울기가 높다)고 할 수 있다.

어떤 알고리즘의 시간복잡도가 Ω(f(n))이라면, 입력크기 n에 대해서 이 알고리즘의 수행시간은 아무리 빨라도 f(n)밖에 되지 않는다는 뜻이다. 즉, 이 알고리즘의 수행시간은 f(n)보다 더 빠를 수는 없다. (f(n)이 하한)

 

 

 

Theta notation(세타 표기법)

---

For a given complexity function f(n), Θ(f(n)) = O(f(n)) ∩ Ω(f(n)). This means that is the set of complexity functions g(n) for which there exists some positive real constants c and d and some nonnegative integer N such that, for all n ≥ N, c × f(n) ≤ g(n) ≤ d × f(n).

 

Example Every-Case Time Complexity for Exchange Sort is that

T(n) = n(n-1)/2 is in both $\text{O}(n^{2})$ and $\Omega(n^{2})$.

This means that T(n) ∈ $\text{O}(n^{2}) \cap \Omega(n^{2}) = \Theta(n^{2}$).

 

👉 주어진 복잡도 함수 f(n)에 대해서 Θ(f(n)) = O(f(n)) ∩ Ω(f(n))이면 다음을 만족한다. 어떤 양의 실수 c, d와 그리고 음이 아닌 정수 N이 존재할 때, 모든 n ≥ N에 대하여 c × f(n) ≤ g(n) ≤ d × f(n)이 성립한다.

 

Meaning of Θ(f(n)) = O(f(n)) ∩ Ω(f(n))

g(n) ∈ Θ(f(n)) 이면 g(n)은 f(n)의 order 라고 한다.  세타(Theta) 표기법은 상술한 big O와 Omega의 교집합을 찾는 것이다.

 

• g(n): 어떤 알고리즘의 분석된 결과
• Θ(f(n)): f(n)의 비율로 증가하는 함수
• g(n)은 f(n)과 같은 정도로 증가한다.
• an asymptotic tight bound: 점근적 상한과 하한의 교집합

 

 

👉 big O는 상한을, Omega는 하한을 찾는 것이므로 실제 알고리즘의 수행시간과는 괴리가 있을 수 있으나, Theta는 big O와 Omega의 교집합으로 시간복잡도를 분석하는데 있어 가장 정확한 표기법이다.

Complexity Categories

---

시간복잡도는 알고리즘의 입력크기 및 단위연산 수행횟수에 관한 함수적 관계식으로 표현 된다. 이때 함수의 증가율을 특정할 수 있는 대표적인 시간복잡도 카테고리는 다음과 같다.

 

 

Θ($1$): constant time

입력크기에 상관없이 수행횟수가 일정

 

Θ($logn$): logarithmic time

 

Θ($n$): linear time

수행시간이 입력 크기에 따라 선형적으로 증가

 

Θ($nlgn$): loglinear time

 

Θ($n^{2}$): quadratic time

 

Θ( $n^{3}$ ): cubic time

 

Θ( $2^{n}$ ): exponential time

 

Θ($n!$): factorial time