Back to : advanced-algorithms
Contents

๊ณ„์‚ฐ์ด๋ก  ์ˆ˜์—…์—์„œ ๋ฐฐ์šด ๋‚ด์šฉ ์ •๋ฆฌ. CLRS CH 17.

Amortized Analysis

์šฐ๋ฆฌ๋Š” ์ผ๋ฐ˜์ ์œผ๋กœ ์–ด๋–ค ์•Œ๊ณ ๋ฆฌ์ฆ˜์„ ๋ถ„์„ํ•  ๋•Œ, $O$, $\Theta$ ๊ฐ™์€ asymptotic์„ ์‚ฌ์šฉํ•ด์„œ ๋ถ„์„ํ•ฉ๋‹ˆ๋‹ค. ์˜ˆ๋ฅผ ๋“ค์–ด, ์—ฐ์‚ฐ ํ•œ๋ฒˆ์— $O(n)$ ์‹œ๊ฐ„์ด ๋“ค๊ณ  ๊ทธ ์—ฐ์‚ฐ์„ $m$๋ฒˆ ํ•ด์•ผ ํ•œ๋‹ค๋ฉด ์ „์ฒด ์‹œ๊ฐ„ ๋ณต์žก๋„๋Š” $O(nm)$์ด ๋  ๊ฒƒ์ž…๋‹ˆ๋‹ค.

์ด ๋ฐฉ๋ฒ•์€ ์œ ์šฉํ•˜์ง€๋งŒ ์–ด๋–ค ์•Œ๊ณ ๋ฆฌ์ฆ˜๋“ค์€ ์ด๋ ‡๊ฒŒ ๋‹จ์ˆœํ•˜๊ฒŒ ๋ถ„์„ํ•  ์ˆ˜ ์—†์Šต๋‹ˆ๋‹ค. ๋Œ€ํ‘œ์ ์ธ ์˜ˆ์‹œ๊ฐ€ C++์˜ vector (dynamic array)์ž…๋‹ˆ๋‹ค.

vector์˜ ๋ชจ๋“  ์—ฐ์‚ฐ์„ ๋ถ„์„ํ•˜์ง€๋Š” ์•Š๋”๋ผ๋„, ์šฐ๋ฆฌ๋Š” ์ผ๋‹จ ์ด ์—ฐ์‚ฐ์„ ์›ํ•ฉ๋‹ˆ๋‹ค.

  • ๋งจ ๋’ค์— pushํ•˜๋Š” ์—ฐ์‚ฐ์ด $O(1)$ ๋น„์Šทํ•œ ์‹œ๊ฐ„์— ์ž‘๋™ํ•˜๊ธฐ๋ฅผ ์›ํ•ฉ๋‹ˆ๋‹ค.
  • ๋งจ ๋’ค์—์„œ popํ•˜๋Š” ์—ฐ์‚ฐ์ด $O(1)$ ๋น„์Šทํ•œ ์‹œ๊ฐ„์— ์ž‘๋™ํ•˜๊ธฐ๋ฅผ ์›ํ•ฉ๋‹ˆ๋‹ค.

์ฆ‰ ์šฐ๋ฆฌ๋Š” ์ผ๋‹จ์€ stack ํ˜•ํƒœ๋กœ ์ƒ๊ฐํ•  ๊ฒƒ์ž…๋‹ˆ๋‹ค. ๊ทธ๋Ÿฌ๋‚˜โ€ฆ

  • ์—ฐ์†ํ•œ ๋ฉ”๋ชจ๋ฆฌ๋งŒ ์‚ฌ์šฉํ•˜์—ฌ, ๋ฐ”๋กœ index๋ฅผ ํ™•์ธํ•  ์ˆ˜ ์žˆ์–ด์•ผ ํ•ฉ๋‹ˆ๋‹ค. stack์„ ๋งํฌ๋“œ ๋ฆฌ์ŠคํŠธ๋กœ ๊ตฌํ˜„ํ•˜๋ฉด ์œ„ ๋‘๊ฐ€์ง€๋ฅผ ์ง€ํ‚ค๊ธฐ ์‰ฝ์ง€๋งŒ, ๋Œ€์‹ ์— vec[17] ๊ฐ™์€ ๊ฒƒ์„ ๋ฐ”๋กœ ํ™•์ธํ•  ์ˆ˜๊ฐ€ ์—†์Šต๋‹ˆ๋‹ค. ๋™์  ๋ฐฐ์—ด์€ ์ด๊ฒƒ์ด ๊ฐ€๋Šฅํ•ด์•ผ ํ•ฉ๋‹ˆ๋‹ค.

๊ทธ๋Ÿฐ๋ฐ, ์ด ๋‘ ์กฐ๊ฑด์€ ๋ญ”๊ฐ€ ์ด์ƒํ•ฉ๋‹ˆ๋‹ค. ๋ฐฐ์—ด์˜ ์›์†Œ๋“ค์ด ์—ฐ์†ํ•œ ๋ฉ”๋ชจ๋ฆฌ๋ฅผ ์ ์œ ํ•ด์•ผ ํ•œ๋‹ค๋ฉด ๊ณ„์† push๋ฅผ ํ•˜๋‹ค๊ฐ€ ์–ธ์  ๊ฐ€๋Š” ๋”์ด์ƒ ๊ทธ ์œ„์น˜์˜ ๋ฉ”๋ชจ๋ฆฌ๋ฅผ ์“ธ ์ˆ˜ ์—†๊ฒŒ ๋˜๊ณ , ๊ทธ๋Ÿฌ๋ฉด ๋ชจ๋“  ์›์†Œ๋“ค์„ ์–ด๋”˜๊ฐ€๋กœ ์˜ฎ๊ฒจ์•ผ ํ•˜๋ฏ€๋กœ ๊ทธ๋•Œ ๋“ค์–ด์žˆ๋Š” ์›์†Œ์˜ ๊ฐœ์ˆ˜๋งŒํผ์˜ ์‹œ๊ฐ„์ด ์†Œ์š”๋  ๊ฒƒ์ž…๋‹ˆ๋‹ค. ๊ทธ๋Ÿฌ๋ฏ€๋กœ, ์—ฐ์†ํ•œ ๋ฉ”๋ชจ๋ฆฌ๋ฅผ ์ ์œ ํ•˜๊ธฐ ์œ„ํ•ด์„  ๋ฐ˜๋“œ์‹œ $O(n)$ ์‹œ๊ฐ„์ด ๊ฑธ๋ฆฌ๋Š” push๊ฐ€ ์กด์žฌํ•ฉ๋‹ˆ๋‹ค.

์ด๋ฅผ ํ•ด๊ฒฐํ•˜๊ธฐ ์œ„ํ•ด, vector๋Š” ๋Œ€๋žต ๋‹ค์Œ๊ณผ ๊ฐ™์€ ๋ฐฉ๋ฒ•์„ ์”๋‹ˆ๋‹ค.

  • size์™€ capacity๋ฅผ ๋ถ„๋ฆฌํ•ฉ๋‹ˆ๋‹ค. size๋Š” ์ง„์งœ ํ˜„์žฌ ๋“ค์–ด ์žˆ๋Š” ์›์†Œ์˜ ๊ฐœ์ˆ˜๋ฅผ, capacity๋Š” ํ• ๋‹น๋œ ๋ฉ”๋ชจ๋ฆฌ๋ฅผ ๋งํ•ฉ๋‹ˆ๋‹ค.
  • ๋งŒ์•ฝ capacity๊ฐ€ ๋‹ค ์ฐจ์ง€ ์•Š์•˜๋‹ค๋ฉด push๊ฐ€ $O(1)$์— ๊ธฐ๋Šฅํ•˜๊ฒŒ ํ•˜๋Š” ๊ฒƒ์€ ์‰ฝ์Šต๋‹ˆ๋‹ค.
  • capacity๊ฐ€ ๋‹ค ์ฐผ๋‹ค๋ฉด, ํ˜„์žฌ ๋ชจ๋“  ์›์†Œ๋“ค์„ ์ƒˆ๋กœ์šด ๊ณณ์œผ๋กœ ์˜ฎ๊ธฐ๋˜, capacity๊ฐ€ ํ˜„์žฌ ํฌ๊ธฐ +1์ด ์•„๋‹ˆ๋ผ ํ˜„์žฌ์˜ ๋‘ ๋ฐฐ๊ฐ€ ๋˜๊ฒŒ ์žก์Šต๋‹ˆ๋‹ค.

์ด๋ ‡๊ฒŒ ํ•˜๋ฉด, move ํ•˜๋Š” ์—ฐ์‚ฐ์ด ๊ฐ€๋”์”ฉ๋งŒ ์ผ์–ด๋‚˜๊ธฐ ๋•Œ๋ฌธ์—, ํ‰๊ท ์ ์œผ๋กœ๋Š” ๋น ๋ฆ…๋‹ˆ๋‹ค. ์ด์™€ ๊ฐ™์ด, ๋งค operation์˜ cost๋ฅผ ์ƒ๊ฐํ•˜๋Š” ๋Œ€์‹ , ์—ฌ๋Ÿฌ operation์˜ cost๋ฅผ ๋ฌถ์–ด์„œ ๊ทธ ํ‰๊ท ์„ ๊ณ„์‚ฐํ•˜๋Š” ๋ฐฉ๋ฒ•์„ amortized analysis๋ผ๊ณ  ๋ถ€๋ฆ…๋‹ˆ๋‹ค.

์ฃผ์˜ํ•  ์ ์€, amortized analysis๋Š” average case์™€๋Š” ๋‹ค๋ฅด๋‹ค๋Š” ์ ์ž…๋‹ˆ๋‹ค. ์•Œ๊ณ ๋ฆฌ์ฆ˜ ๋ถ„์„์€ ๋Œ€๋ถ€๋ถ„ worst case๋ฅผ ๊ธฐ์ค€์œผ๋กœ ํ•˜๋Š”๋ฐ (์ตœ๊ทผ์—๋Š” average case๋„ ๋งŽ์ด ๋‚˜์˜ค๊ธด ํ•ฉ๋‹ˆ๋‹ค), amortized worst case ๋„ ์ƒ๊ฐํ•  ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค. ํ•œ๊ตญ์–ด๋กœ ์ด๋ฅผ ์ž์—ฐ์Šค๋Ÿฝ๊ฒŒ ๋ฐ”๊พธ์ž๋ฉด, โ€œ์ตœ์•…์˜ ๊ฒฝ์šฐ์—๋„ ๊ฐ ์—ฐ์‚ฐ์€ ํ‰๊ท  $O(1)$ ์— ์ž‘๋™ํ•œ๋‹คโ€ ์ž…๋‹ˆ๋‹ค. โ€œํ‰๊ท ์ ์ธ ๊ฒฝ์šฐ์— ํ‰๊ท  $O(1)$โ€ ์ด๋‚˜, โ€œํ‰๊ท ์ ์ธ ๊ฒฝ์šฐ์— ํ•œ๋ฒˆ๋‹น $O(1)$โ€ ๊ณผ๋Š” ๋‹ค๋ฅธ ๋ง์ž…๋‹ˆ๋‹ค.

Three frameworks

Amortized analysis๋ฅผ ํ•˜๋Š” ๋ฐฉ๋ฒ•์—๋Š” ํฌ๊ฒŒ 3๊ฐ€์ง€๊ฐ€ ์žˆ์Šต๋‹ˆ๋‹ค.

Aggregate Method

$n$๋ฒˆ์˜ ์—ฐ์‚ฐ์— ๊ฑธ๋ฆฌ๋Š” ์‹œ๊ฐ„์„ ๋ชจ๋‘ ๋”ํ•œ ๋‹ค์Œ, $n$์œผ๋กœ ๋‚˜๋ˆ•๋‹ˆ๋‹ค. ๊ฐ€์žฅ ๋‹จ์ˆœํ•œ ๋ฐฉ๋ฒ•์ž…๋‹ˆ๋‹ค. ์ด๋ฅผ ์•ž์„œ ์ œ์‹œํ•œ vector์— ์ ์šฉํ•ด ๋ณด๊ฒ ์Šต๋‹ˆ๋‹ค.

๋ฒกํ„ฐ์— $n$๊ฐœ์˜ ์›์†Œ๋ฅผ ์ง‘์–ด๋„ฃ๋Š”๋‹ค๊ณ  ํ•˜๊ฒ ์Šต๋‹ˆ๋‹ค. $n = 2^k$ ์ผ ๋•Œ๋Š” $2^k$ ์˜ ์‹œ๊ฐ„์ด ๋“ค๊ณ , ๊ทธ ์™ธ์—๋Š” 1์˜ ์‹œ๊ฐ„์ด ๋“ ๋‹ค๊ณ  ๊ฐ€์ •ํ•˜๋ฉด, ์ „์ฒด ์‹œ๊ฐ„์€ \(T(n) = n + \sum_{k = 1}^{\log_2 n} 2^k\) ์ด๋ ‡๊ฒŒ ๋  ๊ฒƒ์ž…๋‹ˆ๋‹ค. ๋’ท๋ถ€๋ถ„์˜ $2^k$๋“ค์˜ ํ•ฉ์„ ์ „๋ถ€ ์ทจํ•˜๋ฉด $2n$ ์ดํ•˜์ž„์„ ๋ฐ”๋กœ ์•Œ ์ˆ˜ ์žˆ๊ณ , ์ด๋Š” ์ฆ‰ $n$๋ฒˆ์˜ ์—ฐ์‚ฐ์ด ์ดํ•ฉ $3n$ ์ด์ƒ ๊ฑธ๋ฆฌ์ง€ ์•Š๋Š”๋‹ค๋Š” ๊ฒƒ์ž…๋‹ˆ๋‹ค. ๋”ฐ๋ผ์„œ ๊ฐœ๋ณ„ ์—ฐ์‚ฐ์€ ํ‰๊ท  $O(1)$์ž…๋‹ˆ๋‹ค.

Accounting Method

์–ด๋–ค ์—ฐ์‚ฐ์˜ ์‹ค์ œ cost์™€๋Š” ๋ณ„๊ฐœ๋กœ, ์ด ์—ฐ์‚ฐ์˜ ๊ฐ€๊ฒฉ์„ ์กฐ๊ธˆ ๋„‰๋„‰ํ•˜๊ฒŒ ํ• ๋‹นํ•œ ๋‹ค์Œ, ๋น„์‹ผ ์—ฐ์‚ฐ์„ ํ•  ๋•Œ ์•ž์— ์Ÿ์—ฌ๋†“์€ (?) ์—ฌ๋ถ„์„ ๊ฐ€์ ธ๋‹ค ์“ด๋‹ค๊ณ  ์ƒ๊ฐํ•˜๋Š” ๋ฐฉ๋ฒ•์ž…๋‹ˆ๋‹ค.

์—ญ์‹œ vector์— ์ ์šฉํ•ด ๋ณด๊ฒ ์Šต๋‹ˆ๋‹ค. $n$๊ฐœ์˜ ์›์†Œ๋ฅผ ์ง‘์–ด๋„ฃ๋Š”๋ฐ, ๊ฐœ๋‹น ๋ณดํ†ต์€ 1์ด ๋“ค์ง€๋งŒ ์ผ๋‹จ 3์ด ๋“ ๋‹ค๊ณ  ์ƒ๊ฐํ•˜๊ฒ ์Šต๋‹ˆ๋‹ค. Expansion ์งํ›„์— ๋‚จ์€ credit์€ ๊ณ ๋ คํ•˜์ง€ ์•Š๊ณ , ์ง€๊ธˆ $2^k$๊ฐœ์˜ ์›์†Œ๊ฐ€ ๋“ค์–ด์žˆ๋Š” ํ…Œ์ด๋ธ”์— ์ถ”๊ฐ€๋กœ $n$๊ฐœ๋ฅผ ์ง‘์–ด๋„ฃ๋Š”๋‹ค๊ณ  ์ƒ๊ฐํ•ฉ๋‹ˆ๋‹ค. ์ด๋•Œ, ๊ฐœ๋ณ„ ์—ฐ์‚ฐ์„ ๋„‰๋„‰ํ•˜๊ฒŒ 3์˜ ์‹œ๊ฐ„์ด ๋“ ๋‹ค๊ณ  ํ•˜๋ฉด, $2n$์–ด์น˜๊ฐ€ ๋‚จ์Šต๋‹ˆ๋‹ค. ์˜ˆ์™ธ์ ์œผ๋กœ, $n$๊ฐœ๋ฅผ ์ง‘์–ด๋„ฃ๋‹ค๊ฐ€ ์›์†Œ๊ฐ€ $2^{k+1}$ ๊ฐœ๊ฐ€ ๋˜๋ฉด ์—ฐ์‚ฐ์ด ์‹ค์ œ๋กœ๋Š” $2^{k+1}$ ์‹œ๊ฐ„์ด ๋“ค๊ฒŒ ๋˜๋Š”๋ฐ, ์ด๋Š” ์šฐ๋ฆฌ๊ฐ€ ๊ฐ€์ •ํ•œ cost 3๋ณด๋‹ค ํฝ๋‹ˆ๋‹ค.

๊ทธ๋Ÿฌ๋‚˜, ์—ฌ๊ธฐ๊นŒ์ง€ ์˜ค๋Š” ๊ธธ์— ์šฐ๋ฆฌ๋Š” ์‹ค์ œ๋กœ๋Š” 1๋งŒํผ์ด ๊ฑธ๋ฆฌ๋Š” ์—ฐ์‚ฐ์„ 3์ด๋ผ๊ณ  ๋„‰๋„‰ํ•˜๊ฒŒ ์žก์œผ๋ฉด์„œ $2^k$ ๊ฐœ๋ฅผ ๋„ฃ์–ด ์™”์Šต๋‹ˆ๋‹ค. ์ฆ‰ $2^{k+1}$ ๋งŒํผ ์—ฌ๋ถ„์˜ credit์ด ๋‚จ์•˜์„ ๊ฒƒ์ž…๋‹ˆ๋‹ค. ์ด๋ฅผ ์ด์šฉํ•˜์—ฌ ํ…Œ์ด๋ธ” ํ™•์žฅ์— ํ•„์š”ํ•œ ์‹œ๊ฐ„์„ ์ง€๋ถˆํ•œ๋‹ค๊ณ  ์ƒ๊ฐํ•  ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค. ์ด์™€ ๊ฐ™์ด ์ ๋‹นํ•œ ์—ฌ๋ถ„์„ ๋‘” ๋‹ค์Œ ์ด๋ฅผ ๋‚˜์ค‘์— ์‚ฌ์šฉํ•˜๋Š” ๋ฐฉ๋ฒ•์„ Accounting method๋ผ ํ•ฉ๋‹ˆ๋‹ค.

์ด ๋ฐฉ๋ฒ•์€ ์•ฝ๊ฐ„ ์• ๋งคํ•œ๋ฐ, ์ฒ˜์Œ์— 3์ด๋ผ๋Š” ์• ๋งคํ•œ ์ˆซ์ž๋ฅผ ์–ด๋–ป๊ฒŒ ์žก์„์ง€๋ฅผ ์•Œ๋ ค๋ฉด ๋Œ€์ถฉ ํ‰๊ท ์ ์ธ ์—ฐ์‚ฐ์˜ ๊ฐ€๊ฒฉ์„ ์ฐ์„ ์ˆ˜ ์žˆ์–ด์•ผ ํ•ฉ๋‹ˆ๋‹ค. ๊ทธ๋ž˜์„œ ์ฆ๋ช…ํ•˜๊ธฐ๋Š” ์–ด๋ ต์ง€ ์•Š์ง€๋งŒ, ์ฒ˜์Œ ์ˆ˜์น˜๋ฅผ ์ œ์‹œํ•˜๋Š” ์กฐ๊ธˆโ€ฆ๋ญ๋ž„๊นŒ์š”, ๋น„์ •ํ˜•์ ์ž…๋‹ˆ๋‹ค.

Potential Method

์ด ๊ธ€์„ ์“ฐ๊ฒŒ ๋œ ์ด์œ ์ด์ž, amortized analysis์˜ ํ•ต์‹ฌ์ž…๋‹ˆ๋‹ค.

์ด ์ž๋ฃŒ๊ตฌ์กฐ์˜ ์ƒํƒœ๋ฅผ ๋‚˜ํƒ€๋‚ด๋Š” ์–ด๋–ค potential function $\phi(T)$ ๋ฅผ ์ƒ๊ฐํ•ฉ๋‹ˆ๋‹ค. ์ฆ‰, ํ˜„์žฌ ๋ฒกํ„ฐ์˜ ์ƒํƒœ๋ฅผ ์ˆ˜์น˜๋กœ ํ™˜์‚ฐํ•œ๋‹ค๋Š” ๊ฒƒ์ž…๋‹ˆ๋‹ค. ์ด๋•Œ, ๋‹ค์Œ๊ณผ ๊ฐ™์€ ์กฐ๊ฑด์„ ๋งŒ์กฑํ•˜๊ณ ์ž ํ•ฉ๋‹ˆ๋‹ค.

  • ์ดˆ๊ธฐ ์ƒํƒœ์— 0. ์ฆ‰, $\phi(T_0) = 0$
  • ์–ธ์ œ๋‚˜ $\phi(T_i) \geq 0$. (์‚ฌ์‹ค 2๋ฒˆ ์กฐ๊ฑด์€ ์กฐ๊ธˆ relaxํ•  ์ˆ˜ ์žˆ์ง€๋งŒ, ์•„๋ฌดํŠผโ€ฆ)

์ด์ œ, ๊ฐ ์—ฐ์‚ฐ์€ cost๊ฐ€ ๋“ค ๋ฟ๋งŒ ์•„๋‹ˆ๋ผ, potential function์„ ๋ณ€ํ™”์‹œํ‚ฌ ๊ฒƒ์ž…๋‹ˆ๋‹ค. $i$๋ฒˆ์งธ ์—ฐ์‚ฐ์ด potential function์„ ๋ณ€ํ™”์‹œํ‚ค๋Š” ์–‘์„ $\Delta \phi _i $๋ผ ์“ฐ๋ฉด, ๋‹ค์Œ์ด ์„ฑ๋ฆฝํ•ฉ๋‹ˆ๋‹ค. \(\phi_n = \phi_0 + \Delta \phi_1 + \cdots \Delta \phi_{n}\) ์–ด๋–ค ์—ฐ์‚ฐ์˜ amortized cost $c_i$๋ฅผ, ์‹ค์ œ cost $r_i$์— potential function ๋ณ€ํ™”๋Ÿ‰ $\Delta \phi_i$๋ฅผ ๋”ํ•œ ๊ฐ’์œผ๋กœ ์ƒ๊ฐํ•ฉ๋‹ˆ๋‹ค. ์ฆ‰, $c_i = r_i + \Delta \phi_i$.

$c_i$์˜ ์ดํ•ฉ๊ณผ $r_i$์˜ ์ดํ•ฉ์„ ๋น„๊ตํ•˜๋ฉดโ€ฆ \(\sum c_i = \sum r_i + \sum \Delta \phi_i = \sum r_i + \phi_n - \phi_0 \geq \sum r_i\) ($\phi_n \geq \phi_0 = 0$ ์ด๋ฏ€๋กœ) ๋”ฐ๋ผ์„œ, $c_i$์˜ ํ•ฉ์„ ์–ด๋Š ์ดํ•˜๋กœ ๋ฐ”์šด๋“œ๋ฅผ ์žก์•„์ฃผ๋ฉด ์ด ๋ฐ”์šด๋“œ๊ฐ€ ์‹ค์ œ cost์˜ ํ•ฉ์˜ bound๊ฐ€ ๋ฉ๋‹ˆ๋‹ค.

vector์— ์ ์šฉํ•ด ๋ณด๊ฒ ์Šต๋‹ˆ๋‹ค. vector์˜ potential์€ ํ˜„์žฌ ๋“ค์–ด์žˆ๋Š” ์›์†Œ์˜ ๊ฐœ์ˆ˜ $n_i$ ์™€ vector์˜ ํฌ๊ธฐ $s_i$์— ๋Œ€ํ•ด, $2n_i - s_i$ ๋กœ ์ •์˜ํ•˜๊ธฐ๋กœ ํ•˜๊ฒ ์Šต๋‹ˆ๋‹ค. ์ดˆ๊ธฐ์— ๋ฒกํ„ฐ์— ๋“ค์–ด์žˆ๋Š” ์›์†Œ๊ฐ€ ์—†์„๋•Œ ์•ฝ๊ฐ„ ์ •์˜๊ฐ€ ์• ๋งคํ•œ๋ฐ, ์ดˆ๊ธฐ์˜ size๋ฅผ 0์œผ๋กœ ์žก์œผ๋ฉด ์ด potential function์ด ์œ„ ์กฐ๊ฑด ๋‘๊ฐœ๋ฅผ ๋งŒ์กฑํ•จ์„ ์•Œ ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.

  • $r_i$๊ฐ€ size๋ฅผ ๋ณ€ํ™”์‹œํ‚ค์ง€ ์•Š๋Š” ์—ฐ์‚ฐ์ด๋ผ๋ฉด, ์‹ค์ œ cost๊ฐ€ 1์ด๊ณ  potential์˜ ๋ณ€ํ™”๋Š” $s$๊ฐ€ ๊ทธ๋Œ€๋กœ์ธ ์ฑ„ $n$์ด 1๋งŒํผ ์ฆ๊ฐ€ํ•˜์—ฌ $\Delta \phi = 2$ ์ž…๋‹ˆ๋‹ค.
  • $r_i$๊ฐ€ size๋ฅผ ๋ณ€ํ™”์‹œํ‚จ๋‹ค๋ฉด, $n$์€ 1๋งŒํผ ์ฆ๊ฐ€ํ•˜๋Š”๋ฐ $s$๊ฐ€ 2๋ฐฐ๋กœ ์ฆ๊ฐ€ํ•ฉ๋‹ˆ๋‹ค. ์ด์ „์— $s_{i-1} = n_{i-1}$ ์ด์—ˆ์„ ๊ฒƒ์ด๋ฏ€๋กœ, \((2n_i - s_i) - (2n_{i-1} - s_{i-1}) = (2n_{i-1} + 2 - 2s_{i-1}) - s_{i-1} = 2 - s_{i-1}\) ๋”ฐ๋ผ์„œ $\Delta \phi$ ๋Š” $2 - s_{i-1}$ ์ž…๋‹ˆ๋‹ค. ๊ทธ๋Ÿฐ๋ฐ, ์˜ฎ๊ฒจ์•ผ ํ•˜๋Š” ์›์†Œ๋Š” $s_{i-1}$ ๊ฐœ์ด๊ณ , ์ƒˆ๋กœ ์ถ”๊ฐ€ํ•˜๋Š” 1๊ฐœ๋ฅผ ๊ณ ๋ คํ•˜๋ฉด ์‹ค์ œ cost๋Š” $1 + s_{i-1}$ ์ž…๋‹ˆ๋‹ค. ๋”ฐ๋ผ์„œ $c_i = 3$์ž…๋‹ˆ๋‹ค.

์ด ๋‘ ๊ฒฝ์šฐ ๋ชจ๋‘ amortized cost๊ฐ€ $O(1)$ ์ด๋ฏ€๋กœ ์ „์ฒด๋„ amortized $O(1)$ ์ž…๋‹ˆ๋‹ค.

์ผ๋ฐ˜์ ์œผ๋กœ $c_i$์˜ ํ•ฉ์— ๋Œ€ํ•ด ๋ญ”๊ฐ€๋ฅผ ๋…ผ์˜ํ•˜๋Š” ๊ฒƒ์ด ์‰ฝ๋„๋ก $\phi$๋ฅผ ์ž˜ ์žก๋Š” ๊ฒƒ์„ ๋ชฉํ‘œ๋กœ ํ•ฉ๋‹ˆ๋‹ค. ์ด ๊ฒฝ์šฐ๋Š” worst case์—๋„ ์—ฐ์‚ฐ์ด ํ•œ๊ฐ€์ง€๋ฐ–์— ์—†์–ด์„œ aggregate๋กœ ์‰ฝ๊ฒŒ ํ’€ ์ˆ˜ ์žˆ์ง€๋งŒ, ์—ฌ๊ธฐ์— delete๋งŒ ์ถ”๊ฐ€ํ•˜๋”๋ผ๋„ aggregate๋กœ๋Š” ๋ถ„์„ํ•˜๊ธฐ๊ฐ€ ๊ต‰์žฅํžˆ ์–ด๋ ต์Šต๋‹ˆ๋‹ค.

Dynamic table

๋งŒ์•ฝ ์œ„ vector์— pop๋„ ์ง€์›ํ•ด์•ผ ํ•œ๋‹ค๋ฉด ์–ด๋–จ๊นŒ์š”? ์‚ฌ์‹ค pop์€ ๋งŽ์ด ํ•˜๋”๋ผ๋„ ๋ฉ”๋ชจ๋ฆฌ๋ฅผ ์นจ๋ฒ”ํ•˜์ง€ ์•Š์•„์„œ ๊ทธ๋Œ€๋กœ ํ•˜๋”๋ผ๋„ ์‹œ๊ฐ„ ๋ณต์žก๋„๋Š” ์œ ์ง€๋ฉ๋‹ˆ๋‹ค. ๊ทธ๋Ÿฐ๋ฐ, 100๋งŒ๊ฐœ๋ฅผ ๋„ฃ์—ˆ๋‹ค๊ฐ€ ๋‹ค์‹œ 100๋งŒ๊ฐœ๋ฅผ ๋บ๋Š”๋ฐ vector๊ฐ€ ๊ทธ๋Œ€๋กœ 100๋งŒ์นธ์„ ๋จน๊ณ  ์žˆ๋Š” ๊ฒƒ์€ ๋ญ”๊ฐ€ ๋ชจ์–‘์ƒˆ๊ฐ€ ๋‚˜์ฉ๋‹ˆ๋‹ค. ์ด ๊ฒฝ์šฐ์—๋Š” table์˜ ํฌ๊ธฐ์— ๋น„ํ•ด ์‹ค์ œ ์›์†Œ์˜ ๊ฐœ์ˆ˜ - ์ด๋ฅผ load factor ๋ผ๊ณ  ๋ถ€๋ฆ…๋‹ˆ๋‹ค - ๊ฐ€ ๋„ˆ๋ฌด ๋‚˜๋น ์„œ, ๋ฉ”๋ชจ๋ฆฌ ํšจ์œจ์ด ๋–จ์–ด์ง€๋Š” ๊ฒฝ์šฐ์ž…๋‹ˆ๋‹ค.

์ด๋ฅผ ํ•ด๊ฒฐํ•˜๊ธฐ ์œ„ํ•ด์„œ๋Š”, ์›์†Œ์˜ ๊ฐœ์ˆ˜๊ฐ€ 1/2 ์ดํ•˜๊ฐ€ ๋˜๋ฉด ํ…Œ์ด๋ธ” ํฌ๊ธฐ๋ฅผ ๋ฐ˜์œผ๋กœ ์ค„์ด๋Š” ๋ฐฉ๋ฒ•์„ ๊ฐ€์žฅ ๋จผ์ € ์ƒ๊ฐํ•  ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค. ๊ทธ๋Ÿฌ๋‚˜ ์ด๋ ‡๊ฒŒ ํ•˜๋ฉด, ์›์†Œ์˜ ๊ฐœ์ˆ˜๋ฅผ 1/2๊ฐœ ๊ทผ์ฒ˜๋กœ ์œ ์ง€ํ•˜๋ฉด์„œ push์™€ pop์„ ๋ฐ˜๋ณตํ•˜๋ฉด ํ…Œ์ด๋ธ”์˜ ์ถ•์†Œ์™€ ํ™•๋Œ€๊ฐ€ ์—ฌ๋Ÿฌ๋ฒˆ ์ผ์–ด๋‚˜๊ฒŒ ๋งŒ๋“ค ์ˆ˜ ์žˆ๊ณ , ์ถ•์†Œ/ํ™•๋Œ€๋Š” $O(n)$ ์—ฐ์‚ฐ์ด๋ฏ€๋กœ ๋น„์‹ผ ์—ฐ์‚ฐ์„ ๊ฐ€๋”์”ฉ๋งŒ ํ•œ๋‹ค๋Š” ์‚ฌ์‹ค์„ ์ด์šฉํ•œ๋‹ค ๋Š” amortized ์˜ ๊ฐœ๋…์ด ์ ์šฉ๋˜์ง€ ์•Š์Šต๋‹ˆ๋‹ค. ์‹ค์ œ๋กœ ์ด๋Ÿฌ๋ฉด worst case amortized $O(n)$ ์ด ๋ฉ๋‹ˆ๋‹ค. (Amortized๋Š” average๋ฅผ ๋‚ด๊ธฐ๋Š” ํ•˜์ง€๋งŒ, average case (์ถ•์†Œ/ํ™•๋Œ€๊ฐ€ ๋žœ๋คํ•˜๊ฒŒ ๋ฐœ์ƒ) ๋ฅผ ๋ถ„์„ํ•˜๋Š” ๊ฒƒ์ด ์•„๋‹ˆ๋ผ worst case์˜ average๋„ ๋ถ„์„ํ•  ์ˆ˜ ์žˆ์Œ์„ ์ž˜ ๋ณด์—ฌ์ฃผ๋Š” ์‚ฌ๋ก€์ž…๋‹ˆ๋‹ค)

Load factor๋ฅผ ์ ์ ˆํžˆ ์œ ์ง€ํ•˜๋ฉด์„œ amortized $O(1)$์„ ์ ์šฉํ•˜๋Š” ๋ฐฉ๋ฒ•์€, load factor๋ฅผ ์ตœํ•˜ 1/4๊นŒ์ง€ ํ—ˆ์šฉํ•˜์—ฌ, 1/4 ์ดํ•˜๊ฐ€ ๋˜๋ฉด ํ…Œ์ด๋ธ” ํฌ๊ธฐ๋ฅผ ๋ฐ˜์œผ๋กœ ์ค„์ด๋Š” ๊ฒƒ์ž…๋‹ˆ๋‹ค.

์ด ๋ฐฉ๋ฒ•์ด amortized complexity $O(1)$ ์„ ์œ ์ง€ํ•œ๋‹ค๋Š” ๊ฒƒ์„ aggregate ๊ฐ™์€ ๋ฐฉ๋ฒ•์œผ๋กœ ๋ณด์ด๋ ค๊ณ  ํ•˜๋ฉด ๋งค์šฐ ์–ด๋ ต์Šต๋‹ˆ๋‹ค. ์–ด๋–ค sequence๋กœ ์—ฐ์‚ฐ์ด ์ฃผ์–ด์ง€๋”๋ผ๋„ - ๋ผ๋Š” ๊ฐœ๋…์„ ์ ์šฉํ•˜๊ธฐ๊ฐ€ ์–ด๋ ต๊ธฐ ๋•Œ๋ฌธ์ž…๋‹ˆ๋‹ค. ๋Œ€์‹ ์— potential function์œผ๋กœ ๋‹ค์Œ๊ณผ ๊ฐ™์€ ํ•จ์ˆ˜๋ฅผ ์ƒ๊ฐํ•˜๋ฉด \(\phi = \max(2n_i - s_i, s_i/2 - n_i)\) ์ด๋ฅผ ์ž˜ ์ด์šฉํ•˜์—ฌ amortized cost๋ฅผ ๋ฐ”์šด๋“œํ•  ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค. ์œ„ ํ•จ์ˆ˜๋Š” load factor๊ฐ€ 1/2 ์ด์ƒ์ผ ๋•Œ์™€ ๋ฏธ๋งŒ์ผ ๋•Œ ๊ตฌ๊ฐ„์— ๋”ฐ๋ผ ์ •์˜๋œ ํ•จ์ˆ˜์ด๋ฏ€๋กœ, ์ด 8๊ฐ€์ง€ ๊ฒฝ์šฐ๋ฅผ ๋ถ„์„ํ•ด์•ผ ํ•ฉ๋‹ˆ๋‹ค.

  • load factor 1/2 (์ด์ƒ, ์ดํ•˜) ์ผ ๋•Œ ์ด๋ฅผ ์œ ์ง€ํ•˜๋ฉด์„œ ์‚ฝ์ž…/์‚ญ์ œํ•˜๋Š” ๊ฒฝ์šฐ 4๊ฐ€์ง€
  • load factor 1/2 ์ดํ•˜์—์„œ ์ด์ƒ์œผ๋กœ, ์ด์ƒ์—์„œ ์ดํ•˜๋กœ ๋„˜์–ด๊ฐ€๋Š” ์‚ฝ์ž…๊ณผ ์‚ญ์ œ 2๊ฐ€์ง€
  • load factor 1/4 ์ด์ƒ์—์„œ ์ดํ•˜๋กœ ๋–จ์–ด์ ธ์„œ ์ถ•์†Œ๋ฅผ ์‹œํ–‰ํ•˜๋Š” ์‚ญ์ œ
  • load factor 1์—์„œ ์ถ”๊ฐ€ ์‚ฝ์ž…์œผ๋กœ ์ธํ•ด ํ™•๋Œ€๋ฅผ ์‹œํ–‰ํ•˜๋Š” ์‚ฝ์ž… ์ •๋ง ํ•˜๋‚˜์”ฉ ๋‹ค ๋ถ„์„ํ•˜๋Š” ๊ฒƒ์ด๋ฏ€๋กœ ์ž์„ธํ•œ ๊ณผ์ •์€ ์ƒ๋žตํ•ฉ๋‹ˆ๋‹ค.

Application

๋ณต์žกํ•œ ์—ฐ์‚ฐ์„ ๋‹ค์–‘ํ•˜๊ฒŒ ์ˆ˜ํ–‰ํ•˜๋Š” ์ž๋ฃŒ๊ตฌ์กฐ์—์„œ ๋งค์šฐ ์œ ์šฉํ•ฉ๋‹ˆ๋‹ค.

  • ํ”ผ๋ณด๋‚˜์น˜ ํž™ (์˜ˆ์ „์— ์ œ๊ฐ€ ์“ด ๊ธ€๋„ ์—ฌ๊ธฐ ์žˆ์Šต๋‹ˆ๋‹ค.) ์„ ์ด์šฉํ•˜์—ฌ ๋‹ค์ต์ŠคํŠธ๋ผ ์•Œ๊ณ ๋ฆฌ์ฆ˜์˜ ์‹œ๊ฐ„ ๋ณต์žก๋„๋ฅผ $O(V \log V)$ ๋กœ ๋‚ด๋ฆฌ๊ธฐ
  • Splay Tree ์™€ ๊ฐ™์€ ์ž๋ฃŒ๊ตฌ์กฐ์˜ ๋ณต์žก๋„ ๋ถ„์„.