๊ด€๋ฆฌ ๋ฉ”๋‰ด

Keep Going

Big O Notation ๋ณธ๋ฌธ

Problem Solving

Big O Notation

seon 2023. 4. 7.
๋ฐ˜์‘ํ˜•
๋”๋ณด๊ธฐ

๐Ÿ™‡๐Ÿป‍โ™€๏ธ ์‹œ์ž‘ํ•˜๊ธฐ ์ „ ๊ถ๊ธˆ์ฆ

Q1. ์ข‹์€ ์ฝ”๋“œ๊ฐ€ ๋ญ˜๊นŒ?

Q2. ๋น…์˜ค ๋น…์˜ค ๋น…์˜ค .. ์—„์ฒญ ๋“ค์–ด๋ดค๋Š”๋ฐ ์•Œ๊ณ ๋ฆฌ์ฆ˜ ๊ฐ•์˜์— ์ฒ˜์Œ์— ๋‚˜์˜ฌ ๋งŒํผ ์™œ big O๊ฐ€ ์ค‘์š”ํ•œ๊ฐ€?

[ ๋ชฉํ‘œ ]

1. big O notation์˜ ํ•„์š”์„ฑ์„ ์•Œ๊ธฐ

2. ์™œ ์ค‘์š”ํ•œ๊ฐ€๋ฅผ ์•Œ๊ธฐ

3. ์–ด๋–ป๊ฒŒ ํ‘œํ˜„ํ•˜๋Š”๊ฐ€ ์•Œ๊ธฐ

4. time/space complexity ์ •์˜ํ•  ์ค„ ์•Œ๊ธฐ

5. ์—ฌ๋Ÿฌ๊ฐ€์ง€ ์•Œ๊ณ ๋ฆฌ์ฆ˜์„ big o notation์œผ๋กœ ํ‰๊ฐ€ํ•˜๊ธฐ

6. logarithm์ด ๋ฌด์—‡์ธ์ง€ ์•Œ๊ธฐ

 

[ Big O์— ๋Œ€ํ•ด ๊ฐ€๋ณ๊ฒŒ ์ƒ๊ฐํ•ด๋ณด์ž ]

1. ์ฝ”๋“œ๋ฅผ ์ž‘์„ฑํ•˜๋ ค๊ณ /์ž‘์„ฑํ–ˆ๋Š”๋ฐ ์–ด๋–ค ๋ฐฉ๋ฒ•์ด ์ข‹์€๊ฒƒ์ธ์ง€ ์–ด๋–ป๊ฒŒ ํŒ๋‹จํ•˜์ง€?

=> Big O๊ฐ€ ๊ทธ ํ•ด๊ฒฐ๋ฒ•์ด ๋ ๊ฑฐ์•ผ. Big O๋Š” ๋น„๊ต/์„ฑ๋Šฅํ‰๊ฐ€๊ฐ€ ๊ฐ€๋Šฅํ•œ ์‹œ์Šคํ…œ์ด๊ฑฐ๋“  !

 

2. Big O๋Š” ์ •๋Ÿ‰์ ์ธ ์ฒ™๋„์•ผ.

์•„์ฃผ ์ข‹์•„ / ์ข‹์•„ / ์Œ ๋ณดํ†ต์ธ๋ฐ ? /์Œ ์ด๊ฑด .. / ์œผ ๋ณ„๋กœ์•ผ

์ด๋Ÿฐ ๋А๋‚Œ์ ์ธ ๋А๋‚Œ ์ฒ™๋„ ๋ง๊ณ  ์ •๋Ÿ‰์ ์ธ ์ฒ™๋„๊ฐ€ ํ•„์š”ํ•ด.

 

3. ์™„๋ฒฝํ•œ ์•Œ๊ณ ๋ฆฌ์ฆ˜์ด๋ผ๋Š”๊ฒŒ ์กด์žฌํ• ๊นŒ?

์‚ฌ์‹ค trade-off๋Š” ํ•ญ์ƒ ์กด์žฌํ•ด์„œ ๊ฐ€์žฅ ์™„๋ฒฝํ•œ ๊ฒƒ์ด ๋ฌด์—‡์ด๋ผ๊ณ  ๋”ฑ ์ด์•ผ๊ธฐํ•˜๊ธฐ ์–ด๋ ค์šธ ์ˆ˜ ์žˆ์–ด.

๊ทธ๋Ÿฌ๋‚˜ ๋น„ํšจ์œจ์ ์ธ ๊ฒƒ์ด ๋ฌด์—‡์ธ์ง€ ์•Œ๊ณ , ์ ์–ด๋„ ๊ทธ๊ฒƒ์€ ํ”ผํ•ด์•ผ ์™„๋ฒฝ์— ๊ฐ€๊นŒ์šด ์•Œ๊ณ ๋ฆฌ์ฆ˜์„ ์ž‘์„ฑํ•  ์ˆ˜ ์žˆ๊ฒ ์ง€?

 

[ ๋ฌด์—‡์ด better code์ผ๊นŒ? ]

์–ด๋–ค ๊ด€์ ์ด ์žˆ์„๊นŒ? 1. ์†๋„ 2. ๋ฉ”๋ชจ๋ฆฌ ์‚ฌ์šฉ ์ •๋„ 3. ๊ฐ€๋…์„ฑ ์ •๋„๊ฐ€ ์žˆ๊ฒ ๋‹ค.

1. ๋น ๋ฅธ ์†๋„

2. ์ ์€ memory intensive

3. ๊ฐ€๋…์„ฑ (?๋•Œ๋•Œ๋กœ๋‹ค๋ฆ„?)

 

[ ์†๋„์˜ ๊ด€์ ์—์„œ better code๋ฅผ ์•Œ์•„๋ณด๋Š” ๋ฒ• ]

1. ๊ฑธ๋ฆฐ ์‹œ๊ฐ„์„ ์ธก์ •ํ•ด์„œ ํ•ด๋ณด์ž

=> ์ˆ˜๋™์œผ๋กœ ํƒ€์ด๋จธ๋ฅผ ๋งŒ๋“ค๊ธฐ : perfomance.now();

=> ๋ฌธ์ œ์ ์ด ์žˆ๋‹ค.     

    a. ๊ฐ ๊ธฐ๊ธฐ๋งˆ๋‹ค ๋‹ค๋ฅด๊ณ , ์‹ฌ์ง€์–ด ๊ฐ™์€ ๊ธฐ๊ธฐ์—์„œ๋„ ์กฐ๊ธˆ์”ฉ ๋‹ค๋ฅด๊ฒŒ ๋‚˜์˜จ๋‹ค.

    b. ์ˆซ์ž์˜ ์ฐจ์ด๋‹ˆ๊นŒ ์•Œ๊ณจA์™€ B ๊ฐ๊ฐ ์–ผ๋งˆ ๊ฑธ๋ ธ๋Š”์ง€ ์ˆ˜์น˜๋กœ ์ž‘์„ฑํ•ด์„œ ๋น„๊ตํ•˜๊ธฐ๊ฐ€ ์ฐธ ์• ๋งคํ•˜๋‹ค.

 

2. ์•Œ๊ณ ๋ฆฌ์ฆ˜์˜ ์—ฐ์‚ฐ ๊ฐœ์ˆ˜ ๋‹จ์œ„๋กœ ์–ผ๋งŒํผ์˜ ์‹œ๊ฐ„์ด ๊ฑธ๋ฆด์ง€ ์ถ”์ƒํ™”ํ•ด๋ณด์ž

์ปดํ“จํ„ฐ๊ฐ€ ๋ญ”๊ฐ€๋ฅผ ํ•œ๋‹ค๋Š” ์˜๋ฏธ = ์—ฐ์‚ฐ์„ ํ•œ๋‹ค = CPU๋ฅผ ์‚ฌ์šฉํ•œ๋‹ค.

"์—ฐ์‚ฐ 1๊ฐœ"๋ฅผ ์ฒ˜๋ฆฌํ•˜๋Š” ์‹œ๊ฐ„์ด ๋ชจ๋‘ ๊ฐ™๋‹ค๋Š” ์ „์ œ๊ฐ€ ์„ฑ๋ฆฝํ•œ๋‹ค๋ฉด ์•Œ๊ณ ๋ฆฌ์ฆ˜์˜ ์—ฐ์‚ฐ ๊ฐœ์ˆ˜๋ฅผ ๋น„๊ตํ•˜์—ฌ ์•Œ๊ณ ๋ฆฌ์ฆ˜ ์„ฑ๋Šฅ์„ ํ‰๊ฐ€ํ•  ์ˆ˜ ์žˆ๋‹ค. + = / * - ์ด๋Ÿฐ๊ฒƒ๋“ค์€ ๋ชจ๋‘ ์—ฐ์‚ฐ ๋‹จ์œ„๋‹ค. ํ•˜์ง€๋งŒ ์—ฐ์‚ฐ ๊ฐœ์ˆ˜๋ฅผ ๋‹ค ๊ณ„์‚ฐํ•œ๋‹ค๋Š” ๊ฒƒ์€ hard !!!

 

3. Big O

    a. ์• ๋งคํ•œ counting์„ ํ˜•์‹ํ™”ํ•ด์ฃผ๋Š” ๋ฐฉ๋ฒ•

    b. ์ž…๋ ฅ์˜ ํฌ๊ธฐ์™€ ์‹คํ–‰์‹œ๊ฐ„์˜ ๊ด€๊ณ„๋ฅผ ์˜๋ฏธํ•œ๋‹ค ? 

    c. ์ „์ฒด์ ์ธ ๊ทธ๋ฆผ์„ ๋ณด๊ธฐ ์œ„ํ•œ ๋ฐฉ๋ฒ•์ด๋‹ค. n^2 + 5n + 8 => O(n^2)

    ํ‘œ๊ธฐ๋ฒ• : O(f(n)) | ๊ฐ€์žฅ ์˜ค๋ž˜ ๊ฑธ๋ฆฌ๋Š” ๊ฒƒ ๊ธฐ์ค€์ธ ๊ฐœ๋…์ด๋‹ค. ์ผ๋ฐ˜์ ์œผ๋กœ๋Š” ์ž๋ฆฟ์ˆ˜์ •๋„๋งŒ ๊ณ ๋ คํ•œ๋‹ค (?) 

 

4. Big O shorthands

 

[ ๊ณต๊ฐ„๋ณต์žก๋„ ]

n์ด ์ปค์งˆ์ˆ˜๋ก ๊ณต๊ฐ„์˜ ์ž…์žฅ์—์„œ ๋ฌด์Šจ์ผ์ด ์ƒ๊ธฐ๋‚˜์š”?์— ์˜๋ฏธ๋ฅผ ๊ฐ€์ง€๊ณ  ์žˆ๋Š” ๊ณต๊ฐ„๋ณต์žก๋„ ! 

1. booleans numbers undefined null์€ constant space๋‹ค.

2. string์€ O(n)์˜ ๊ณต๊ฐ„์„ ์š”๊ตฌํ•œ๋‹ค. (n์€ string length)

3. reference, array, object ํƒ€์ž…์€ ๋ชจ๋‘ O(n)

 

[ Logarithm Complexity ]

O(1) O(logn) O(n) O(nlogn) O(n^2)

 

 

 

๋ฐ˜์‘ํ˜•