๐ง Lower Bound
Upper Bound๋ ๋น ์ค ํ๊ธฐ๋ฒ์ ์ฌ์ฉํด ๋ณด์๋ค๋ฉด ์ด๋ฏธ ์์ค ๊ฒ์ด๋ผ ์๊ฐํฉ๋๋ค.
Lower Bound ์ญ์ ์ด์ ๋น์ทํฉ๋๋ค.
์ด๋ค ๋ฌธ์ ๊ฐ ์ฃผ์ด์ก์ ๋, `ํด๋น ๋ฌธ์ ๋ฅผ ํด๊ฒฐํ๋ ์๊ณ ๋ฆฌ์ฆ์ Lower Bound๊ฐ T์ด๋ค.`์ ์๋ฏธ๋ ๋ค์๊ณผ ๊ฐ์ต๋๋ค.
(์ด๋ค ๊ฐ์ ํ์์) ํด๋น ๋ฌธ์ ๋ฅผ T ์๊ฐ๋ณด๋ค ๋ ๋นจ๋ฆฌ ํด๊ฒฐํ ์ ์๋ค.
์ด๋ ๊ฐ์ ์ ๊ณ์ฐ ๋ชจ๋ธ, ์ถ๊ฐ ์ฌ์ฉ ๊ณต๊ฐ ๋ฑ์ ์ฌ๋ฌ๊ฐ์ง ๊ฐ์ ์ด ์์ ์ ์์ต๋๋ค.
๋ํ ๋น -์ค๋ฉ๊ฐ(Ω) ํ๊ธฐ๋ฒ์ ์ฌ์ฉํ์ฌ ํ๊ธฐํฉ๋๋ค.
์์๋ฅผ ํ๋ ์ดํด๋ณด๊ฒ ์ต๋๋ค.
๊ธธ์ด n์ธ ๋ฐฐ์ด์์ ์ต๋๊ฐ์ ์ฐพ๋ ์๊ณ ๋ฆฌ์ฆ์ lower bound๋ Ω(1)์ด๋ผ๊ณ ํํํ ์๋ ์๊ณ , Ω(n)์ด๋ผ ํํํ ์๋ ์์ต๋๋ค.
์ด ๊ฒฝ์ฐ Ω(n)์ผ๋ก ๋ํ๋ด๋ ๊ฒ์ด ๋ ์ฐ์ํ(์ ์ฉํ) Lower Bound๊ฐ ๋ฉ๋๋ค.
๐ง Optimal Algorithm
์ด๋ค ๋ฌธ์ ๋ฅผ ํด๊ฒฐํ๋ ์๊ณ ๋ฆฌ์ฆ์ Upper Bound์ Lower Bound๊ฐ ์ผ์นํ๋ ๊ฒฝ์ฐ,
ํด๋น Upper Bound๋ฅผ ๊ฐ์ง๋ ์๊ณ ๋ฆฌ์ฆ์ ์๋ฏธํฉ๋๋ค.
์ด๋ค ๋ฌธ์ ๋ฅผ T ์๊ฐ ์์ ํด๊ฒฐํ๋ Optimal Algorithm์ ์กด์ฌ๋ฅผ ์ฆ๋ช ํ๋ ๋ฐฉ๋ฒ์ ๋ค์๊ณผ ๊ฐ์ต๋๋ค.
- T ์๊ฐ ์์ ๋ฌธ์ ๋ฅผ ํด๊ฒฐํ๋ Algorithm์ ๋์์ธํฉ๋๋ค. (์ด๋ Upper Bound๋ฅผ ๊ตฌํ๋ ๊ฒ๊ณผ ๊ฐ์ต๋๋ค.)
- ํด๋น ์๊ณ ๋ฆฌ์ฆ์ Lower Bound๊ฐ T์์ ์ฆ๋ช ํฉ๋๋ค.
๐ง Adversary Argument
Optimal Algorithm์ ์ฆ๋ช ํ๊ธฐ ์ํด์๋ Lower Bound๋ฅผ ๊ตฌํ๋ ๋ฐฉ๋ฒ์ด ํ์ํฉ๋๋ค.
Adversary Argument๋ Lower Bound๋ฅผ ์ฆ๋ช ํ ์ ์๋ ์ฌ๋ฌ ๋ฐฉ๋ฒ๋ค ์ค ํ๋์ ๋ฐฉ๋ฒ์ ๋๋ค.
Adversay Argument๋ Solver์ Adversary๊ฐ์ ์ด๋ฃจ์ด์ง๋ ์ค๋ฌด๊ณ ๊ฐ ๊ฒ์๊ณผ ๋น์ทํ ๋๋์ ๊ฒ์์ด๋ผ ์๊ฐํ ์ ์์ต๋๋ค.
์งํ์ ๋ค์๊ณผ ๊ฐ์ด ์ด๋ฃจ์ด์ง๋๋ค.
Adversary๋ input(์ ๋ต)์ ๊ฐ์ง๊ณ ์์ผ๋ฉฐ, solver๋ ํด๋น input์ด ๋ฌด์์ธ์ง ํ์ธํ ์ ์์ง๋ง Adversary์๊ฒ ์ง๋ฌธ์ ํ ์๋ ์์ต๋๋ค.
(์ง๋ฌธ์ ํ์ ์ ์ฝ์ ๊ณ์ฐ ๋ชจ๋ธ์ ์ ์ฝ๊ณผ ๋์ผํฉ๋๋ค.)
Adversary๋ Solver์ ์ง๋ฌธ์ ๋ํด ๋๋ต์ ํด์ผ ํ๋ฉฐ, Solver๊ฐ ๋ฌธ์ ๋ฅผ ํด๊ฒฐํ๊ธฐ ์ด๋ ต๊ฒ ํ๊ธฐ ์ํด input์ ๊ณ์ ๋ฐ๊ฟ ์ ์์ต๋๋ค.
๊ทธ๋ฌ๋ input์ ๋ฐ๊ฟ ๋์๋ ์ด์ ์ ์ง๋ฌธ์ ๋ํ ๋ต๋ณ์ ๋ํ์ฌ ์ผ๊ด์ฑ(Consistently)์ ์ ์งํด์ผ ํฉ๋๋ค.
Algorithm์ Lower Bound๋ Solver์๊ฒ ํ์ํ ์ต์ํ์ ์ง๋ฌธ ํ์๊ฐ ๋ฉ๋๋ค.
๋ช ๊ฐ์ง ์์๋ค์ ํตํด ์ดํด๋ณด๋๋ก ํ๊ฒ ์ต๋๋ค.
๐ง ์์ 1 : ์ต๋๊ฐ ์์น ์ฐพ๊ธฐ
Problem : Array[1, .., 5] ์์ Maximum Element์ ์์น ์ฐพ๊ธฐ
๋ฐฐ์ด์ ์ธ๋ฑ์ค๋ 1๋ถํฐ ์์ํ๊ณ , Array์ ๊ฐ Element๋ ๋ชจ๋ ๋ค๋ฅด๋ค๊ณ ๊ฐ์ ํ๊ฒ ์ต๋๋ค.
์ง๋ฌธ์ ํ์(๊ณ์ฐ ๋ชจ๋ธ)์ ๋ค์๊ณผ ๊ฐ์ต๋๋ค.
A์ i๋ฒ์งธ element๋ j๋ฒ์งธ element๋ณด๋ค ํฐ๊ฐ?
(A[i] > A[j])
3๋ฒ์งธ ์์๊ฐ 2๋ฒ์งธ ์์๋ณด๋ค ํฌ๋ค๊ณ ๋๋ต์ ํ์ผ๋ฏ๋ก, input์ 5, 4, 3, 10, 7๋ก ๋ฐ๊พผ ๊ฒฝ์ฐ ํด๋น ๋๋ต์ ๋ชจ์์ด ๋ฉ๋๋ค.
๋ฐ๋ผ์ ์ด์ ๊ฐ์ด๋ ๋ฐ๊ฟ ์ ์์ต๋๋ค.
์ฆ ์ด๋ฅผ ํตํด Solver๋ ์ต์ 4๋ฒ์ ์ง๋ฌธ์ด ํ์ํจ์ ์ ์ ์์ผ๋ฉฐ, ์ด๋ฅผ ํตํด ํด๋น Problem์ Lower Bound๋ 4๋ผ๋ ๊ฒ์ ์ ์ ์์ต๋๋ค.
๋ง์ฝ 4๋ฒ๋ณด๋ค ์ ๊ฒ ๋น๊ตํ๋ค๋ฉด ๋์๊ด๊ณ๋ฅผ ์ ์ ์๋ ๋ ๊ฐ ์ด์์ Element๊ฐ ์กด์ฌํ๊ฒ ๋๋ฉฐ, Adversary๋ ํด๋น Element๋ฅผ ์์๋ก ๋ฐ๊ฟ์ผ๋ก์จ ์ ๋ต์ ๋ง์ถ์ง ๋ชปํ๊ฒ ํ ์ ์์ต๋๋ค.
๐ง ์์ 1์ ๋ณํ : ์ต๋๊ฐ ์์น ์ฐพ๊ธฐ
์ ๊ณผ์ ์ ๋ค์๊ณผ ๊ฐ์ด ๋ค์ ํํํด ๋ณด๋๋ก ํ๊ฒ ์ต๋๋ค.
์ฐ์ Directed Graph๋ฅผ ํ๋ ์ ์ํ๋๋ก ํ๊ฒ ์ต๋๋ค.
G = (V, E)
V = {1, 2, 3, 4, 5}
E = A[i] > A[j] ๋ผ๋ ๋๋ต์ Adversary์๊ฒ ๋ฐ์ ๋๋ง๋ค edge(j, i)๋ฅผ E์ ์ถ๊ฐ.
๋ฐ๋ผ์ G์ edge์ ๊ฐ์ = ํ์ฌ๊น์ง ์ํํ ๋น๊ต ํ์
์๋ฅผ ๋ค์ด 3๋ฒ์ ์ง๋ฌธ์ ํตํด
A[1] < A[4],
A[2] < A[3],
A[3] < A[5] ๋ผ๋ ๋๋ต์ ๋ฐ์๋ค๊ณ ํ๋ฉด, ๋ค์๊ณผ ๊ฐ์ต๋๋ค.
์ด๋ Solver๊ฐ ๋ต์ ํ๊ธฐ ์ํด์๋ ์ต์ 4๊ฐ์ edge๊ฐ ํ์ํ๋ค๋ ๊ฒ์ ์ ์ ์์ต๋๋ค.
๊ทธ๋ ์ง ์๋ค๋ฉด ์ต์ ๋๊ฐ์ Connected Component๊ฐ ์์ฑ๋๊ณ ,
์๋ก ๋ค๋ฅธ ๋ Component์ ์ํ ๋ ์ ์ (์์ ์์์์๋ A[4]์ A[5])์ Adversary๊ฐ ๋ง์๋๋ก ๋ฐ๊ฟ ์ ์์ต๋๋ค.
(A[4]์ A[5] ์ฌ์ด์๋ ์๋ฌด๋ฐ topology๊ฐ ์กด์ฌํ์ง ์๊ธฐ ๋๋ฌธ์ ๋๋ค.)
์ด์ ๊ฐ์ ๋ฐฉ๋ฒ์ผ๋ก Size n์ธ array์ ๊ฒฝ์ฐ n-1์ด Lower Bound์ธ ๊ฒ์ ์ฆ๋ช ํ ์ ์์ต๋๋ค.
๐ง ๋๋ค๋ฅธ ๋ฐฉ๋ฒ : ์ต๋๊ฐ ์์น ์ฐพ๊ธฐ
Adversary Argument๋ฅผ ์ด์ฉํ๋, ๋ค๋ฅธ ๋ฐฉ๋ฒ์ผ๋ก Lower Bound๋ฅผ ์ฆ๋ช ํด ๋ณด๋๋ก ํ๊ฒ ์ต๋๋ค.
Adversary์ ์ํ์ฌ A[j] > A[i]๋ผ๊ณ ํ๋ช ๋ ๊ฒฝ์ฐ, j๋ i๋ฅผ ์ด๊น(i๋ j์๊ฒ ์ง)์ด๋ผ๊ณ ํ ๋ค, Array Position Set({1, 2, 3, 4, 5})์ ๋ค์๊ณผ ๊ฐ์ด ์ธ ๊ฐ์ ์งํฉ์ผ๋ก Partition ํ๋๋ก ํ๊ฒ ์ต๋๋ค.
W : ํ ๋ฒ ์ด์ ์ด๊ฒผ์ผ๋ฉฐ, ํ ๋ฒ๋ ์ง์ง ์์ position๋ค์ ์งํฉ
L : ํ ๋ฒ ์ด์ ์ง position๋ค์ ์งํฉ
N : ํ ๋ฒ๋ ๋น๊ตํ์ง ์์ position๋ค์ ์งํฉ
์ ์์ ์ํด ์ด๊ธฐ ์ํ๋ W์ L์ ∅(๊ณต์งํฉ)์ด๋ฉฐ, N = {1, 2, 3, 4, 5}์ ๋๋ค.
N์ด ∅์ด๊ณ , L์ ํฌ๊ธฐ๊ฐ n-1์ธ ๊ฒฝ์ฐ W์ ์กด์ฌํ๋ ์ ์ผํ position์ด ์ต๋๊ฐ์ position์ด ๋ฉ๋๋ค.
N์ ํฌ๊ธฐ๊ฐ 1 ์ค๊ฑฐ๋, L์ ํฌ๊ธฐ๊ฐ 1 ์ฆ๊ฐํ ๋๋ง๋ค 1 credit์ ์ป๋๋ค๊ณ ๊ฐ์ ํ๋ฉด, ๋ฌธ์ ๋ฅผ ํด๊ฒฐํ๊ธฐ ์ํด์๋ ์ต์ 4 x 2 + 1 = 9 credit์ด ํ์ํฉ๋๋ค.
์ด์ ์ง๋ฌธ์ ๋ํ์ฌ ์ป์ ์ ์๋ ์ต์ credit์ ์ ๋ฆฌํ ํ๋ฅผ ์ดํด๋ณด๋๋ก ํ๊ฒ ์ต๋๋ค.
๊ฐ๋ฅํ ์ต์ํ์ ์ฐ์ฐ์ผ๋ก 9 credit์ ๋ฒ๊ธฐ ์ํด Solver๋ ๋ง์ Credit์ ์ฃผ๋ ๊ฒ ๋ถํฐ Greedyํ๊ฒ ์ ํํ ์ ์์ต๋๋ค.
์ฆ ์ฒ์ ๋ ๋ฒ์ (N ,N)์ ์์นํ ๋ position์ ๋น๊ตํฉ๋๋ค. (6 credit)
์ ๋ ๋ฒ์ ๋น๊ต๊ฐ ๋๋ ๊ฒฝ์ฐ, N์๋ ํ๋์ ์์๋ง์ด ์กด์ฌํ๊ธฐ ๋๋ฌธ์, (N, N) ๋น๊ต๋ฅผ ๋๋ค์ ์งํํ ์๋ ์์ต๋๋ค.
์ฆ ์ดํ์๋ ๋ค๋ฅธ ์ฐ์ฐ๋ค๋ง์ ์ํํด์ผ ํ๋ฉฐ, 9 credit์ ๋ฒ๊ธฐ ์ํด์๋ ์ต์ 4๋ฒ์ ์ง๋ฌธ์ด ํ์ํ๋ค๋ ๊ฒ์ ์ ์ ์์ต๋๋ค.
๋ง์ฝ size n์ธ array์ ๋ํ์ฌ, ๋ฌธ์ ๋ฅผ ํด๊ฒฐํ๊ธฐ ์ํด์๋ $(n-1) \times 2 + 1 = 2n - 1$ credit์ด ํ์ํ๋ฉฐ (N, N)๋น๊ต๋ $\left \lfloor \frac{n}{2} \right \rfloor$ ๋ฒ ๋ง์ด ๊ฐ๋ฅํฉ๋๋ค.
๋ฐ๋ผ์ $3 \times \left \lfloor \frac{n}{2} \right \rfloor$ credit์ ์ป์ ์ ์์ต๋๋ค.
์ดํ์๋ ์ง์์ ๊ฒฝ์ฐ N์ ๋์ด์ ๋จ์์๋ ์์๊ฐ ์์ผ๋ฏ๋ก credit 1์ ์ฃผ๋ ๋น๊ต(W, W)๋ง์ ์ํํ ์ ์๊ณ ,
๋ฐ๋ผ์ $\frac{n}{2} - 1$ ๋ฒ์ ์ถ๊ฐ ์ฐ์ฐ์ด ํ์ํฉ๋๋ค.
ํ์์ ๊ฒฝ์ฐ N์๋ ์์๊ฐ ํ๋ ๋จ์ผ๋ฏ๋ก credit 2๋ฅผ ์ฃผ๋ ๋น๊ต๋ฅผ 1ํ ์ํํ ์ ์์ผ๋ฉฐ,
์ดํ credit 1์ ์ฃผ๋ ์ฐ์ฐ(W, W)์ $\left \lfloor \frac{n}{2} \right \rfloor - 1$ ๋ฒ ๋ ์ํํด์ผ ํฉ๋๋ค.
๋ฐ๋ผ์ ๋ ๊ฒฝ์ฐ ๋ชจ๋ lower bound๊ฐ n-1์ ๋๋ค.
๐ง ์์ 2 : ์ต๋๊ฐ๊ณผ ์ต์๊ฐ ์์น ์ฐพ๊ธฐ
์์ ์์๋ฅผ ์กฐ๊ธ ๋ ํ์ฅ์์ผ, ํด๋น ๋ฌธ์ ๋ฅผ ์๊ฐํด ๋ณด๋๋ก ํ๊ฒ ์ต๋๋ค.
Problem : ๊ธธ์ด n์ธ ๋ฐฐ์ด A[1, ..., n] ์์ ์ต๋๊ฐ๊ณผ ์ต์๊ฐ์ position์ ์ฐพ๊ธฐ.
์ฐ์ ๊ธฐ๋ณธ์ ์ผ๋ก ์๊ฐํ ์ ์๋ ๋ฐฉ๋ฒ์ ์ต๋๊ฐ๊ณผ ์ต์๊ฐ์ ๊ฐ๊ฐ n-1๋ฒ์ ๋น๊ต์ ๊ฑธ์ณ ์ฐพ๋ ๋ฐฉ๋ฒ์ ์๊ฐํ ์ ์์ต๋๋ค.
์ด ๊ฒฝ์ฐ ๋น๊ต ํ์๋ 2(n-1) ์ ๋๋ค.
๊ทธ๋ฌ๋ ์ต๋๊ฐ์ ์ฐพ์ ํ, ์ต๋๊ฐ์ ์ ์ธํ ์์๋ค ์ค์์ ์ต์๊ฐ์ ์ฐพ๋๋ค๋ฉด n-1 + n-2 = 2n -3๋ฒ์ ๋น๊ต ํ์๋ฉด ์ถฉ๋ถํฉ๋๋ค.
์กฐ๊ธ ๋ ์ฑ๋ฅ์ ํฅ์์์ผ๋ณธ๋ค๋ฉด, ๋ชจ๋ n๋ณด๋ค ์์ ํ์ i์ ๋ํ์ฌ, A[i]์ A[i+1]์ ๋น๊ตํ ํ W์ L์ ๊ฐ๊ฐ ๋ค์๊ณผ ๊ฐ์ ์งํฉ์ผ๋ก ์ ์ํ๊ฒ ์ต๋๋ค.
W : ๋ ์ค ๋ ํฐ ๊ฐ์ ์ ์ฅํ ์์น
L : ๋ ์ค ๋ ์์ ๊ฐ์ ์ ์ฅํ ์์น
W์ ์ํ position๋ค ์ค ๊ฐ์ฅ ํฐ ๊ฐ์ ์ ์ฅํ position๊ณผ, L์ ์ํ position๋ค ์ค ๊ฐ์ฅ ์์ ๊ฐ์ ์ ์ฅํ position์ด ๊ฐ๊ฐ ์ต๋๊ฐ์ ์์น์ ์ต์๊ฐ์ ์์น๊ฐ ๋ฉ๋๋ค.
์ด ๊ฒฝ์ฐ ์ด ๋น๊ต ํ์๋ $\frac{n}{2} + \frac{n}{2} - 1 + \frac{n}{2} - 1 = \frac{3n}{2}-2$ ์ ๋๋ค.
์ ์๊ณ ๋ฆฌ์ฆ์ด Optimal Algorithm์ธ์ง ์์๋ณด๊ธฐ ์ํด Adversary Argument๋ฅผ ์ฌ์ฉํ์ฌ Lower Bound๋ฅผ ๊ตฌํด๋ณด๋๋ก ํ๊ฒ ์ต๋๋ค.
์์ Find Max์ ๊ฒฝ์ฐ์ ๋ง์ฐฌ๊ฐ์ง๋ก, Credit์ ์ด์ฉํด์ ์ฆ๋ช ํ ์ ์์ต๋๋ค.
์ด๋ฒ์๋ A์ position๋ค์ ์งํฉ์ ๋ค์ 4๊ฐ์ ์งํฉ์ผ๋ก partitionํ๋๋ก ํ๊ฒ ์ต๋๋ค.
U : ํ ๋ฒ๋ ๋น๊ตํ์ง ์์ Position๋ค์ ์งํฉ
W : ํ ๋ฒ๋ ์ง์ง ์์ Position๋ค์ ์งํฉ
L : ํ ๋ฒ๋ ์ด๊ธฐ์ง ๋ชปํ Position๋ค์ ์งํฉ
N : ํ ๋ฒ ์ด์ ์ด๊ธฐ๊ณ , ํ ๋ฒ ์ด์ ์ง Position๋ค์ ์งํฉ
Solver์๊ฒ ์ฃผ์ด์ง ์ด๊ธฐ ์ํ๋ U = {1, 2, ..., n} ์ด๋ฉฐ, W์ L, N ์ ∅(๊ณต์งํฉ)์ ๋๋ค.
|U| = 0, |W| = |L| = 1, |N| = n-2 ์ผ ๋ solver๋ ๋ฌด์กฐ๊ฑด ์ ๋ต์ ๋ง์ถ ์ ์์ต๋๋ค.
์ด์ ์ด๋ค position์ด ํ ์งํฉ์์ ๋ค๋ฅธ ์งํฉ์ผ๋ก ์ฎ๊ฒจ์ง๋ ๊ฒฝ์ฐ 1credit์ ์ป๋๋ค๊ณ ํ๊ฒ ์ต๋๋ค.
์ด๋ ์ด๋ค position์ด ์งํฉ N์ ๊ฐ๊ธฐ ์ํด์๋ ๋ฐ๋์ set W๋ L์ ๊ฑฐ์ณ๊ฐ์ผ ํฉ๋๋ค. (์ฆ 2 credit์ด ํ์ํฉ๋๋ค.)
๋ฐ๋ผ์ solver๊ฐ ๋๋ตํ๊ธฐ ์ํด์๋ ์ ์ด๋ 2(n - 2) + 2(U์์ W, U์์ L 1๋ฒ ์ฉ) = 2n - 2 credit์ด ํ์ํฉ๋๋ค.
Solver๋ (U, U)๋น๊ต๋ฅผ ์ต๋ $\frac{n}{2}$ ๋ฒ ์ํํ ์ ์์ต๋๋ค. ์ฆ ์ด๋ฅผ ํตํด n credit์ ์ป์ ์ ์์ต๋๋ค.
์ด์ 2n - 2 - n = n - 2 credit์ด ๋จ์๋๋ฐ, ์ด ๊ฒฝ์ฐ U์ ์ํ ๋ position์ด ์กด์ฌํ์ง ์๊ธฐ ๋๋ฌธ์ Solver๋ ์๋ฌด๋ฆฌ ์ต์ ์ ๋น๊ต๋ฅผ ํ๋๋ผ๋ 1๋ฒ ๋น๊ต์ 1 credit๋ฐ์ ์ป์ง ๋ชปํฉ๋๋ค.
๋ฐ๋ผ์ ๋๋จธ์ง n-2 credit์ ์ป๊ธฐ ์ํด์๋ ์ต์ํ n - 2๋ฒ์ ๋น๊ต๊ฐ ํ์ํฉ๋๋ค.
์ฆ ๋ฌธ์ ๋ฅผ ํด๊ฒฐํ๊ธฐ ์ํด์๋ ์ต์ $\frac{n}{2} + (n- 2) = \frac{3n}{2} -2$ ๋ฒ์ ๋น๊ต๊ฐ ํ์ํฉ๋๋ค.
๐ง ์์ 3 : Comparision Based Sortiong
Problem : Comparison model ํ์์ ๊ธธ์ด n์ธ ๋ฐฐ์ด A[1, 2, ..., n]์ sorting ํ๊ธฐ
ํธ์์ A์ ๋ชจ๋ Element๋ ์๋ก ๋ค๋ฅด๋ค๊ณ ํ๊ฒ ์ต๋๋ค.
๐ comparision model
๋ ์์น(position) i, j์ ๋ํ์ฌ, A[i]์ A[j]๋ฅผ ๋น๊ตํ์ฌ, 'A[i] > A[j]' ํน์ 'A[i] < A[j]'์ ๋ต์ ์ป๋ ์ฐ์ฐ๊ณผ,
๋ ์์น๋ฅผ swapํ๋ ์ฐ์ฐ๋ง์ด ๊ฐ๋ฅํ๋ฉฐ,
๋ค๋ฅธ ๋ชจ๋ ์ฐ์ฐ์ ์ฌ์ฉ ๋ถ๊ฐ๋ฅํ model์ ์๋ฏธํฉ๋๋ค.
๐ Upper Bound
Comparision-Based Sorting์ Upper Bound๋ O(n log n) ์ ๋๋ค.
In-place heap sort๋ฅผ ์ฌ์ฉํ์ฌ ๊ฐ๋ฅํฉ๋๋ค.
๐ Lower Bound
ํธ์๋ฅผ ์ํด A๋ฅผ ์๋์ ๊ฐ์ด 1์์ n๊น์ง์ ์์ด(permutation) P[1, 2, ..., n]์ผ๋ก ๋ณํํ๊ฒ ์ต๋๋ค.
์ด๋ P[i] = j๊ฐ ์๋ฏธํ๋ ๊ฒ์ A[i]๋ A์์ j๋ฒ์งธ๋ก ์์ ์์์ ์๋ฏธํฉ๋๋ค.
์ด ๊ฒฝ์ฐ A๋ฅผ sorting ํ๋ ๋ฌธ์ ๋ P๋ฅผ ๊ตฌํ๋ ๋ฌธ์ ์ ๋์ผํด์ง๋๋ค.
์ด์ Lower Bound๋ฅผ ๊ตฌํ๊ธฐ ์ํด ๋ค์๊ณผ ๊ฐ์ Full Binary Decision Tree๋ฅผ ์ ์ํ๊ฒ ์ต๋๋ค.
Decision Tree์ non-leaf node๋ค์ comparision ์ฐ์ฐ์ ๋ํ๋ ๋๋ค.
Decision Tree์ leaf node ๋ค์ ํน์ permutation์ ๋ํ๋ ๋๋ค.
Decision Tree์ Root๋ก๋ถํฐ non-leaf node์ ์กด์ฌํ๋ comparison์ ๊ฒฐ๊ณผ์ ๋ฐ๋ผ ๋ ๊ฐ์ ์ค ํ๋๋ฅผ ์ ํํ์ฌ ์๋๋ก ๋ด๋ ค๊ฐ๊ฒ ๋๋ฉฐ, ๋ง์ง๋ง leaf node์ ์๋ permutation์ root๋ก๋ถํฐ ์ํํ๋ comparison์ ๋๋ต์ ๋ชจ๋ ๋ง์กฑํด์ผ ํฉ๋๋ค.
์๋ฅผ ๋ค์ด ๊ธธ์ด 3 permutation์ ๊ฒฐ์ ํธ๋ฆฌ๋ ์๋์ ๊ฐ์ต๋๋ค.
์ด์ ๋ํ์ฌ Adversary Argument๋ฅผ ์ ์ฉํ ์ ์์ต๋๋ค.
Decision Tree์ root์์ ์ถ๋ฐํ์ฌ ๊ฐ node์ ํด๋นํ๋ ์ง๋ฌธ์ Solver๊ฐ ํ ๋ค, Solver๋ ํด๋น ์ง๋ฌธ์ ๋ต์ ๋ฐ๋ผ ์ด๋ํ subtree์ ์ํ leaf node๋ค ์ค ํ๋๊ฐ ๋ต์ด๋ผ๋ ๊ฒ์ ์ ์ ์์ต๋๋ค.
๋ฐ๋๋ก Adversary๋ ํด๋น subtree์ ์ํ leaf node๋ค ์ค์ ํ๋๋ก input์ ๋ณ๊ฒฝํ ์ ์์ต๋๋ค.
๊ฒฐ๊ตญ Solver๊ฐ ์ ํํ๊ฒ ๋ต์ ์๊ธฐ ์ํด์๋ decision tree์ subtree์ size๊ฐ 1์ด ๋ ๋ ๊น์ง(์ฆ leaf node์ ๋๋ฌํ ๋๊น์ง) ๊ณ์ํด์ ์ง๋ฌธ์ ํด์ผ ํฉ๋๋ค.
์ฆ Lower Bound๋ Decision Tree์ ์ต๋ Depth๊ฐ ๋ฉ๋๋ค.
Decision Tree์ Leaf node์ ์ = P์ ๋ชจ๋ ๊ฒฝ์ฐ์ ์ = n!
Depth๊ฐ d์ธ binary tree๋ ์ต๋ $2^d$ ๊ฐ์ leaf node๋ฅผ ๊ฐ์ง ์ ์์ผ๋ฏ๋ก, Decision Tree์ depth๋ ์ต์ log(n!)์ด ๋์ด์ผ ํฉ๋๋ค.
n! ~ O($n^n$)์ ์ฌ์ฉํ์ฌ decision tree์ depth๋ ๋งค์ฐ ํฐ n์ ๋ํ์ฌ Ω(n log n)์ด ๋จ์ ์ ์ ์์ต๋๋ค.
'๐ฅ Computer Science > ์๊ณ ๋ฆฌ์ฆ' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[์๊ณ ๋ฆฌ์ฆ] Reduction (0) | 2022.12.05 |
---|---|
[์๊ณ ๋ฆฌ์ฆ] Counting Sort (๊ณ์ ์ ๋ ฌ) (0) | 2022.12.05 |
[์๊ณ ๋ฆฌ์ฆ] DP(4) - ํ๋ก์ด๋ ์์ฌ(Floyd Warshall) ์๊ณ ๋ฆฌ์ฆ (0) | 2022.11.13 |
[์๊ณ ๋ฆฌ์ฆ] DP (3) - ๋ฒจ๋งํฌ๋(Bellman-Ford) ์๊ณ ๋ฆฌ์ฆ (0) | 2022.11.12 |
[์๊ณ ๋ฆฌ์ฆ] DP (2) - Edit Distance(ํธ์ง ๊ฑฐ๋ฆฌ) (0) | 2022.11.12 |