๐Ÿ•ข ๋ณต์žก๋„

๊ฒฝ์ดยท2022๋…„ 6์›” 23์ผ
0

๐Ÿ•ข ๋ณต์žก๋„๋ž€?

  • ๋ณต์žก๋„ : ์•Œ๊ณ ๋ฆฌ์ฆ˜์˜ ์„ฑ๋Šฅ์„ ๋‚˜ํƒ€๋‚ด๋Š” ์ฒ™๋„
  • ์‹œ๊ฐ„ ๋ณต์žก๋„ : ์•Œ๊ณ ๋ฆฌ์ฆ˜์„ ์œ„ํ•ด ํ•„์š”ํ•œ ์—ฐ์‚ฐ์˜ ํšŸ์ˆ˜
  • ๊ณต๊ฐ„ ๋ณต์žก๋„ : ์•Œ๊ณ ๋ฆฌ์ฆ˜์„ ์œ„ํ•ด ํ•„์š”ํ•œ ๋ฉ”๋ชจ๋ฆฌ์˜ ์–‘
  • ๋ณต์žก๋„๊ฐ€ ๋‚ฎ์„์ˆ˜๋ก ์ข‹์€ ์•Œ๊ณ ๋ฆฌ์ฆ˜์ด๋‹ค.

๐Ÿ•ข ๋น…์˜ค(Big-O) ํ‘œ๊ธฐ๋ฒ•

๊ฐ€์žฅ ๋น ๋ฅด๊ฒŒ ์ฆ๊ฐ€ํ•˜๋Š” ํ•ญ๋งŒ ๊ณ ๋ คํ•˜๋Š” ํ‘œ๊ธฐ๋ฒ•์œผ๋กœ ํ•จ์ˆ˜์˜ ์ƒํ•œ๋งŒ์„ ๋‚˜ํƒ€๋‚ด๋Š” ํ‘œ๊ธฐ๋ฒ•


๐Ÿ•ข ์‹œ๊ฐ„ ๋ณต์žก๋„(Time Complexity)

์•Œ๊ณ ๋ฆฌ์ฆ˜์„ ์ˆ˜ํ–‰ํ•˜๋Š” ๋ฐ ์—ฐ์‚ฐ๋“ค์ด ๋ช‡ ๋ฒˆ ์ด๋ฃจ์–ด์ง€๋Š” ์ง€๋ฅผ ๋‚˜ํƒ€๋‚ด๋Š” ์ˆซ์ž

โœ” ์‹œ๊ฐ„ ์ œํ•œ์ด 1์ดˆ์ผ๋•Œ

N์˜ ๋ฒ”์œ„๊ฐ€ 500์ธ ๊ฒฝ์šฐ : ์‹œ๊ฐ„ ๋ณต์žก๋„๊ฐ€ O(N^3)์ธ ์•Œ๊ณ ๋ฆฌ์ฆ˜ ์„ค๊ณ„
N์˜ ๋ฒ”์œ„๊ฐ€ 2,000์ธ ๊ฒฝ์šฐ : ์‹œ๊ฐ„ ๋ณต์žก๋„๊ฐ€ O(N^2)์ธ ์•Œ๊ณ ๋ฆฌ์ฆ˜ ์„ค๊ณ„
N์˜ ๋ฒ”์œ„๊ฐ€ 100,000์ธ ๊ฒฝ์šฐ : ์‹œ๊ฐ„ ๋ณต์žก๋„๊ฐ€ O(NlogN)์ธ ์•Œ๊ณ ๋ฆฌ์ฆ˜ ์„ค๊ณ„
N์˜ ๋ฒ”์œ„๊ฐ€ 10,000,000์ธ ๊ฒฝ์šฐ : ์‹œ๊ฐ„ ๋ณต์žก๋„๊ฐ€ O(N)์ธ ์•Œ๊ณ ๋ฆฌ์ฆ˜ ์„ค๊ณ„


๐Ÿ•ข ๊ณต๊ฐ„ ๋ณต์žก๋„(Space Complexity)

ํ”„๋กœ๊ทธ๋žจ์„ ์‹คํ–‰์‹œํ‚จ ํ›„ ์™„๋ฃŒํ•˜๋Š” ๋ฐ ํ•„์š”๋กœ ํ•˜๋Š” ์ž์› ๊ณต๊ฐ„์˜ ์–‘

โœ” ๋ฆฌ์ŠคํŠธ ํฌ๊ธฐ์— ๋”ฐ๋ฅธ ๋ฉ”๋ชจ๋ฆฌ ์‚ฌ์šฉ๋Ÿ‰

int a[1,000] : 4KB
int a[1,000,000] : 4MB
int a[2,000][2,000] : 16MB

profile
์ด์‚ฌ์ค‘์ž…๋‹ˆ๋‹ค!๐ŸŒŸhttps://velog.io/@devkyoung2

0๊ฐœ์˜ ๋Œ“๊ธ€