Notice
Recent Posts
Recent Comments
Link
ยซ   2024/11   ยป
์ผ ์›” ํ™” ์ˆ˜ ๋ชฉ ๊ธˆ ํ† 
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
Archives
Today
Total
๊ด€๋ฆฌ ๋ฉ”๋‰ด

Lennon FE

[JS] ์ž๋ฐ”์Šคํฌ๋ฆฝํŠธ ๋ฐฐ์—ด ์‹œ๊ฐ„ ๋ณต์žก๋„ ๋ณธ๋ฌธ

๐Ÿง‘‍๐Ÿ’ป Web/JavaScript

[JS] ์ž๋ฐ”์Šคํฌ๋ฆฝํŠธ ๋ฐฐ์—ด ์‹œ๊ฐ„ ๋ณต์žก๋„

Lennon 2022. 1. 28. 12:15
728x90
๋ฐ˜์‘ํ˜•

์ž๋ฐ”์Šคํฌ๋ฆฝํŠธ ๋ฐฐ์—ด ๋ฉ”์„œ๋“œ์˜ ์‹œ๊ฐ„ ๋ณต์žก๋„๋ฅผ ์•Œ์•„๋ณด์ž.

 

์‹œ๊ฐ„ ๋ณต์žก๋„๋ฅผ ํ‘œ๊ธฐํ•  ๋• ๋Œ€์ฒด๋กœ ๋น…์˜ค ํ‘œ๊ธฐ๋ฒ•์œผ๋กœ ์‚ฌ์šฉํ•œ๋‹ค.

๋น…์˜ค ํ‘œ๊ธฐ๋ฒ•์— ๋Œ€ํ•ด ๊ฐ„๋‹จํ•˜๊ฒŒ ์„ค๋ช…ํ•˜์ž๋ฉด

 

O(1)

์ƒ์ˆ˜ ์‹œ๊ฐ„ ๋ณต์žก๋„์ด๋‹ค. 

function twoUp(num) {
  return num+num;
}

num์— ์–ด๋–ค ์ˆ˜๊ฐ€ ๋“ค์–ด์™€๋„ + ํ•œ๋ฒˆ์˜ ์—ฐ์‚ฐ์„ ์‹œ๋„ํ•œ๋‹ค. ์—ฐ์‚ฐ์ด ์—ฌ๋Ÿฌ ๋ฒˆ ์‹œํ–‰๋˜๋„ ์‹œ๊ฐ„ ๋ณต์žก๋„๋Š” O(1)๋กœ ๋™์ผํ•˜๋‹ค.

๋ฌดํ•œ๋Œ€๋ฅผ ๊ธฐ์ค€์œผ๋กœ ๋ดค์„ ๋•Œ ๊ทธ๋ž˜ํ”„ ํ˜•์‹์€ ๋น„์Šทํ•˜๊ธฐ ๋•Œ๋ฌธ์— ๋™์ผํ•˜๊ฒŒ ํ‘œ๊ธฐํ•˜๋Š” ๊ฑธ ๊ทœ์น™์œผ๋กœ ํ•œ๋‹ค.

function upupup(num) {
  return num+num+num+num+num+num+num+num+num+num+num+num+num+num+num;
}

O(logN)

logN๋งŒํผ์˜ ์‹œ๊ฐ„ ๋ณต์žก๋„์ด๋‹ค. ๊ฐ„๋‹จํ•œ ์˜ˆ๋กœ 2๊ฐœ์˜ ์ž์‹๋…ธ๋“œ๋ฅผ ๊ฐ€์ง€๋Š” ์ด์ง„ํŠธ๋ฆฌ๋ฅผ ์ด์šฉํ•ด 8๊ฐœ์˜ ๋…ธ๋“œ์ค‘ ์›ํ•˜๋Š” ๊ฐ’์˜ ๋…ธ๋“œ๋ฅผ ์ฐพ๋Š”๋‹ค๊ณ  ์ƒ๊ฐํ•ด๋ณด์ž. ๊ทธ๋Ÿผ 2๊ฐœ์˜ ์ž์‹๋…ธ๋“œ๋กœ ์ธํ•ด 8 => 4 => 2 => 1 ์ˆœ์„œ๋กœ ์ฐพ์„ ์ˆ˜ ์žˆ์„ ๊ฒƒ์ด๋‹ค. ์ด๋Š” ๋‚˜์ค‘์— ๋”ฐ๋กœ ์ •๋ฆฌํ•ด๋ณด๊ฒ ์Šต๋‹ˆ๋‹ค.

 

O(N)

n๋งŒํผ์˜ ์‹œ๊ฐ„ ๋ณต์žก๋„์ด๋‹ค. ๊ฐ„๋‹จํ•˜๊ฒŒ for๋ฌธ์„ ์ƒ๊ฐํ•˜๋ฉด ๋œ๋‹ค.

function count(num) {
  let count = 0;
  for(let i = 1; i <= num; i++){
    if(i%2 === 1) {
      count += 1;
    }
  }
  return count;
}

O(1)๊ณผ ๋‹ค๋ฅด๊ฒŒ num์ด 10,000์ด๋ผ๋ฉด 10,000๋ฒˆ ์ˆœํšŒํ•˜๊ณ , 1,000,000์ด๋ผ๋ฉด 1,000,000๋ฒˆ ์ˆœํšŒํ•œ๋‹ค. ์ฆ‰ num๋งŒํผ ์ˆœํšŒํ•˜๋ฏ€๋กœ O(n)์œผ๋กœ ํ‘œ๊ธฐํ•  ์ˆ˜ ์žˆ๋‹ค. ๋งˆ์ฐฌ๊ฐ€์ง€๋กœ 4๊ฐœ์˜ for๋ฌธ์ด ์žˆ์–ด๋„ O(4n)์ด ์•„๋‹ˆ๋ผ ๊ทธ๋ƒฅ O(n)์œผ๋กœ ํ‘œ๊ธฐํ•œ๋‹ค.

 

O(NlogN)

N*logN๋งŒํผ์˜ ์‹œ๊ฐ„ ๋ณต์žก๋„, ๋ฐ‘์—์„œ ์ •๋ ฌ ํŒŒํŠธ์—์„œ ์„ค๋ช…ํ•˜๊ฒ ์Šต๋‹ˆ๋‹ค.

 

O(N^2)

n^2๋งŒํผ์˜ ์‹œ๊ฐ„ ๋ณต์žก๋„ ๋Œ€ํ‘œ์ ์œผ๋กœ 2์ค‘ for๋ฌธ์ด ์žˆ๋‹ค.

function matrix(num) {
  const mat = [];
  for(let i = 0; i < num; i++){
    const row = [];
    for(let j = 0; j < num; j++) {
      row.push([i,j]);
    }
    mat.push(row);
  }
}

์œ„ ์ฝ”๋“œ์—์„œ num์ด 1000์ด๋ผ ์ƒ๊ฐํ•ด๋ณด์ž, ์–ผํ• ๋ด๋„ 1,000,000๋ฒˆ ์‹คํ–‰๋œ๋‹ค๋Š” ๊ฑธ ์•Œ ์ˆ˜ ์žˆ๋‹ค. ๋‹ค๋ฅธ ๋ณต์žก๋„์— ๋น„ํ•ด ๋งŽ์€ ์‹œ๊ฐ„์ด ๊ฑธ๋ฆฌ๋ฏ€๋กœ

์ˆ˜ํ•™์  ๊ณต์‹ ๋“ฑ์„ ํ™œ์šฉํ•ด ํšจ์œจ์ ์œผ๋กœ ์‚ฌ์šฉํ•˜๋Š” ๊ฒŒ ์ข‹๋‹ค.


๋ฐฐ์—ด์—์„œ์˜ ์‹œ๊ฐ„ ๋ณต์žก๋„

์šฐ์„  ๋ฐฐ์—ด์—์„œ ์šฐ๋ฆฌ๊ฐ€ ์ž์ฃผ ์‚ฌ์šฉํ•˜๋Š” ํ•จ์ˆ˜ ๋ฐ ๋ฉ”์„œ๋“œ๋“ค์„ ์‚ดํŽด๋ณด์ž.

push ๋ฐฐ์—ด์˜ ๋งจ ๋์— ๊ฐ’์„ ์‚ฝ์ž…ํ•œ๋‹ค.
pop ๋ฐฐ์—ด์˜ ๋งจ ๋์˜ ๊ฐ’์„ ์‚ญ์ œํ•œ๋‹ค.
shift ๋ฐฐ์—ด์˜ ๋งจ ์•ž์— ๊ฐ’์„ ์‚ฝ์ž…ํ•œ๋‹ค.
unshift ๋ฐฐ์—ด์˜ ๋งจ ์•ž์˜ ๊ฐ’์„ ์‚ญ์ œํ•œ๋‹ค.
concat ๋ฐฐ์—ด์„ ์ด์–ด์ค€๋‹ค.
slice ๋ฐฐ์—ด์„ ์ง€์ •ํ•ด๋†“์€ ์˜์—ญ๋ถ€๋ถ„์œผ๋กœ ์ž๋ฅธ๋‹ค.
splice ๋ฐฐ์—ด์— ์ง€์ •ํ•ด๋†“์€ ์ธ๋ฑ์Šค์— ๊ฐ’๋“ค์„ ์ถ”๊ฐ€ํ•˜๊ฑฐ๋‚˜, ์ž๋ฅธ๋‹ค.
sort ๋ฐฐ์—ด์„ ์ •๋ ฌํ•œ๋‹ค.
forEach, map, filter, reduce ๋ฐฐ์—ด์— ์‚ฌ์šฉํ•˜๋Š” ์ฃผ ๋ฉ”์„œ๋“œ ๋“ค

 

push, pop : O(1) 

๋ฐฐ์—ด์€ ์šฐ๋ฆฌ๊ฐ€ ์•Œ๋‹ค์‹œํ”ผ ์ธ๋ฑ์Šค๋ฅผ ๊ฐ€์ง„๋‹ค. ์ฒซ ์‹œ์ž‘์€ 0, ๋์˜ ์ธ๋ฑ์Šค ๊ฐ’์€ ๋ฐฐ์—ด์˜ ๊ธธ์ด -1์ด๋‹ค. push, pop์€ ๋ฐฐ์—ด์˜ ๋งจ ๋์— ๊ฐ’์„ ์ถ”๊ฐ€ ๋ฐ ์‚ญ์ œ ํ•˜๋ฏ€๋กœ ์ธ๋ฑ์Šค ํ•˜๋‚˜๋งŒ ์ง€์ •ํ•ด์ฃผ๊ฑฐ๋‚˜ ์‚ญ์ œํ•˜๋ฉด ๋œ๋‹ค. ์‹œ๊ฐ„ ๋ณต์žก๋„๋Š” O(1) ์ด๋‹ค.

 

shift, unshift : O(N)

์•ž์—๋‹ค ๊ฐ’์„ ์‚ฝ์ž…ํ•˜๊ฑฐ๋‚˜ ์‚ญ์ œํ•˜๋Š” shift, unshift๋Š” ๋ฐฐ์—ด์˜ ์ธ๋ฑ์Šค์— ๋งŽ์€ ์˜ํ–ฅ์„ ๋ผ์นœ๋‹ค. ์˜ˆ๋กœ ์•ž์˜ ๊ฐ’์„ ์ถ”๊ฐ€ํ•œ๋‹ค๊ณ  ์ƒ๊ฐํ•ด๋ณด์ž.

 

[ 1, 2, 3, 4, 5 ]

   0   1   2   3   4                 

 

ํ•ด๋‹น ๋ฐฐ์—ด ์•ž์— 0 ๊ฐ’์„ ์ถ”๊ฐ€ํ•˜๋ฉด ์ธ๋ฑ์Šค๋Š” ์•ž์œผ๋กœ ํ•œ ์นธ์”ฉ ๋ฐ€๋ฆฌ๊ณ  ๋’ค์— ํ•˜๋‚˜๊ฐ€ ์ถ”๊ฐ€๋  ๊ฒƒ์ด๋‹ค.

 

[ 0, 1, 2, 3, 4, 5 ]

   0   1   2   3   4   5

 

์ด๋ ‡๊ฒŒ ๊ฐ’์„ ์•ž์— ์ถ”๊ฐ€ํ•จ์œผ๋กœ ์ธํ•ด ์ „์ฒด ์ธ๋ฑ์Šค๊ฐ€ ๋ฐ”๋€Œ๋ฏ€๋กœ ์‹œ๊ฐ„ ๋ณต์žก๋„๋Š” O(N) ์ด๋‹ค.

 

concat, slice, splice : O(N)

๋ฐฐ์—ด์„ ์ด์–ด์ฃผ๊ณ , ์ž๋ฅด๊ณ , ๊ฐ’์„ ์ถ”๊ฐ€ํ•˜๋ฉด ์ธ๋ฑ์Šค๋ฅผ ์กฐ์ •ํ•ด์ค˜์•ผํ•˜๋ฏ€๋กœ O(N)์œผ๋กœ ์ƒ๊ฐํ•˜๋ฉด ํŽธํ•˜๋‹ค.

 

forEach, map, filter, reduce :  O(N)

๋ฐฐ์—ด์˜ ๋ฉ”์„œ๋“œ๋„ ๊ฒฐ๊ตญ ๋ฐฐ์—ด์˜ ๊ธธ์ด๋งŒํผ ๋ฐฐ์—ด์„ ์ˆœํšŒํ•ด์•ผํ•˜๋ฏ€๋กœ O(N)์œผ๋กœ ์ƒ๊ฐํ•˜๋ฉด ๋œ๋‹ค.

sort : O(NlogN)

์ธ์ž๊ฐ’์œผ๋กœ ๋„˜์–ด์˜จ ํ•จ์ˆ˜์— ๋”ฐ๋ผ ๊ฐ’์„ ์ •๋ ฌํ•œ๋‹ค. ๊ธฐ๋ณธ์ ์œผ๋กœ ๋‚ด์žฅ sort๋ฅผ ์‚ฌ์šฉํ•  ๋•Œ ํฌ๋กฌ์—์„œ ํ€ต ์ •๋ ฌ์„ ์‚ฌ์šฉํ•œ๋‹ค.

ํ‰๊ท ์ ์œผ๋กœ NlogN์˜ ์‹œ๊ฐ„ ๋ณต์žก๋„๋ฅผ ๊ฐ€์ง„๋‹ค. ์ž์„ธํ•œ ๊ฑด ๋‹ค์Œ์— ์ •๋ ฌ์— ๋Œ€ํ•œ ์‹œ๊ฐ„๋ณต์žก๋„๋ฅผ ์•Œ์•„๋ณผ ๋•Œ ํฌ์ŠคํŒ…ํ•˜๋„๋ก ํ•˜๊ฒ ์Šต๋‹ˆ๋‹ค.

const arr = [1,26,76,85,3];

arr.sort((a, b) => a - b);

console.log(arr) // [1, 3, 26, 76, 85]

 

๋ฐฐ์—ด์˜ ๋‚ด์žฅ ํ•จ์ˆ˜ ๋ฐ ๋งค์„œ๋“œ์— ๋Œ€ํ•œ ์‹œ๊ฐ„ ๋ณต์žก๋„๋ฅผ ์•Œ์•„๋ดค๋‹ค. ์™ ๋งŒํ•ด์„œ shift, unshift๋ณด๋‹ค๋Š” push, pop์„ ์ด์šฉํ•˜๋Š” ๊ฒŒ ์‹œ๊ฐ„์ ์œผ๋กœ ์œ ๋ฆฌํ•œ ๊ฑธ ์•Œ ์ˆ˜ ์žˆ๋‹ค.

728x90
๋ฐ˜์‘ํ˜•
Comments