์ผ | ์ | ํ | ์ | ๋ชฉ | ๊ธ | ํ |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | ||
6 | 7 | 8 | 9 | 10 | 11 | 12 |
13 | 14 | 15 | 16 | 17 | 18 | 19 |
20 | 21 | 22 | 23 | 24 | 25 | 26 |
27 | 28 | 29 | 30 | 31 |
- ๋คํธ์ํฌ ํต์ ์์ฒญ
- Call Stack
- java
- styled-components ์ค์น ์ค๋ฅ
- react
- styled-components extension
- ๋จ์ผ๋งํฌ๋๋ฆฌ์คํธ
- Javascript
- fetch()
- styled-components ๋ฒ์ ๋ฌธ์
- react-native-snap-carousel
- ๋ธ๋์น ์ด๋ฆ ๋ณ๊ฒฝ ๋ช ๋ น์ด
- ์ต๋จ๊ฑฐ๋ฆฌ์๊ณ ๋ฆฌ์ฆ
- reading 'useDebugValue'
- react immer
- Code Splitting
- carouselButton
- git branch -m
- Styled Components
- React ๊ณต์๋ฌธ์
- styled-compoents
- ํ ์คํฌ ํ
- 1966 ํ๋ฆฐํฐํ
- reading 'edgesOut'
- vscode extension
- javascript ๋น๋๊ธฐ
- use-immer
- styled components ์ค์น ์๋จ
- likelion
- js fetch
- Today
- Total
Keep Going
Big O Notation ๋ณธ๋ฌธ
๐๐ปโ๏ธ ์์ํ๊ธฐ ์ ๊ถ๊ธ์ฆ
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)
'Problem Solving' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[BOJ] 18870 ์ขํ ์์ถ (1) | 2024.04.22 |
---|---|
[BOJ] 1966 ํ๋ฆฐํฐ ํ (0) | 2024.04.15 |
์๊ณ ๋ฆฌ์ฆ ์ฑ๋ฅ ํ๊ฐ์ python ์ ์๋ฃํ (0) | 2023.11.09 |
[Baekjoon/C] ๋ฐฑ์ค 1008๋ฒ A/B (0) | 2019.08.27 |
๊ธฐ์์ ๋ ฌ (0) | 2019.04.07 |