๐ ๊ฐ๋ฐ ๊ณต๋ถ 9๊ฐ์ ์ฐจ์ธ to-be ๊ฐ๋ฐ์์ ์์ต blog๐๏พ Mar 27 ~ 02, 2022
ํ์ฌ ์ํ
๊ฐ๋จ ๊ฐ๋ ์ ๋ํด ๊น์ด ์๋ ๋ด์ฉ ํ์ต ์์ 1
์๊ฐ ๋ณต์ก๋์ ๊ณต๊ฐ ๋ณต์ก๋๋ฅผ ํตํด code๊ฐ ๋์๋ ๋์ ๊ตฌ๋ ์๋๊ฐ ์ผ๋ง๋ ๋น ๋ฅธ์ง, ์ผ๋ง๋ memory ๊ณต๊ฐ์ ์ฐจ์งํ๋์ง ์ค๋ช ํ ์ ์๋ค. ํ์ง๋ง JavaScript๋ก๋ ๊ณต๊ฐ ๋ณต์ก๋๋ฅผ ๋ค๋ฃจ๊ธฐ์ ์ ์ ํ์ง ์์ผ๋ฏ๋ก ์๊ฐ ๋ณต์ก๋๋ง ๋ค๋ฃจ๊ธฐ๋ก ํ๋ค.
๐งโ ์ ๊ณต๊ฐ๋ณต์ก๋๋ฅผ ๋ค๋ฃจ๊ธฐ์ ์ ์ ํ์ง ์์ง? JavaScript๋ memory ์ฌ์ฉ๊ฐ์ ๊ฑธ ๊ฐ๋ฐ์๊ฐ ํ๋ ๊ฒ ์๋๋ผ JavaScript๊ฐ ์์์ ํด์ฃผ๊ธฐ ๋๋ฌธ์ ๊ทธ๋ฐ๊ฐ? ๐ง
code์ ํจ์จ์ฑ์ ์ํ์ ์ผ๋ก ํํํ๋ ๊ฒ์ด๋ค.
ref. ฮฉ (omega), ฮ (theta), ฮ (omicron)
์๊ฐ ๋ณต์ก๋๋ ๋์ถํ๊ณ ์ ํ๋ ๊ฐ์ด ์ด๋์ ์๋์ง, ์ด๋ป๊ฒ ์ฐพ๋์ง์ ๋ฐ๋ผ best case์ worst case๊ฐ ์๋๋ฐ Big-ฮ๋ worst case๋ฅผ ๊ธฐ์ค์ผ๋ก ํ๋ค.
๐งโ ์ค๋ช ์ด ๋ค๋ฅด๋ค. ๋ ธ๋ง๋ ์ฝ๋๋์ ํ๊ท ์ ๊ธฐ์ค์ผ๋ก ํ๋ค๊ณ ํ๋๋ฐ! ๋ค๋ฅธ ์ค๋ช ์ ์ฐพ์๋ณด๋
๋ผ๊ณ ํ๋ฉฐ ๊ฐ๋ฅํ๋ฉด worst casee๋ฅผ ๊ธฐ์ค์ผ๋ก programmingํ๋ ๊ฒ์ด ๋ง์ฝ์ ๋๋นํ๊ธฐ ์ข๋ค๊ณ ํ๋ค. ๐ง
์ด์ด ์ข๊ฒ ๊ฒฐ๊ณผ๋ฅผ ๋น ๋ฅด๊ฒ ๋์ถํ ์ ์๊ฒ ์ง๋ง ์ค์ service๋ฅผ ๊ตฌํํ ๋ ๋ณด์์ ์ผ๋ก ์ ๊ทผํ๋ ๊ฒ์ด ์์ ํ๊ธฐ ๋๋ฌธ์ worst case๋ฅผ ๊ธฐ์ค์ผ๋ก ์๊ฐํ๋ ๊ฒ์ด ์ข๋ค.
โป ์ฑ๋ฅ์ ํฐ ์ํฅ์ ์ฃผ์ง ์์ผ๋ฏ๋ก ์์๋ ๋ฌด์ํ๋ค.
ย ย ย ย e.g. O(2N) โ O(N), O(Nโด) โ O(Nยฒ)
input (๋ฌธ์ ์ ํฌ๊ธฐ) ๋งํผ ์์ ์๊ฐ์ด ๋์ด๋๋ค.
ref. arr.shift()
, arr.unshift()
, arr.splice()
// ๐ต n๋งํผ ์คํ
const logItems = (n) => {
for (let i = 0; i < n; i++) {
console.log(i);
}
};
logItems(7);
// โฌ๏ธ Output
// 0
// 1
// 2
// 3
// 4
// 5
// 6
// ๐ต 2n๋งํผ ์คํ
const logItems = (n) => {
for (let i = 0; i < n; i++) {
console.log(i);
}
for (let j = 0; j < n; j++) {
console.log(j);
}
};
logItems(7);
// โฌ๏ธ Output
// 0
// 1
// 2
// 3
// 4
// 5
// 6
// 0
// 1
// 2
// 3
// 4
// 5
// 6
input (๋ฌธ์ ์ ํฌ๊ธฐ) ๋งํผ ์์ ์๊ฐ์ด ๊ธฐํ๊ธ์์ ์ผ๋ก ๋์ด๋๋ค.
๋นํจ์จ์ ์ธ ํ์ด๋ฒ์ด๋ค.
// ๐ต 4^2 (4*4) ๋งํผ ์คํ (n^2 (n*n))
const logItems = (n) => {
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) {
console.log(i, j);
}
}
};
logItems(4);
// โฌ๏ธ Output
// 0 0
// 0 1
// 0 2
// 0 3
// 1 0
// 1 1
// 1 2
// 1 3
// 2 0
// 2 1
// 2 2
// 2 3
// 3 0
// 3 1
// 3 2
// 3 3
// ๐ต 4^3 (4*4*4) ๋งํผ ์คํ (n^3 (n*n*n))
const logItems = (n) => {
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) {
for (let k = 0; k < n; k++) {
console.log(i, j, k);
}
}
}
};
logItems(4);
// โฌ๏ธ Output
// 0 0 0
// 0 0 1
// 0 0 2
// 0 0 3
// 0 1 0
// 0 1 1
// 0 1 2
// 0 1 3
// ... (๋๋ฌด ๊ธธ์ด์ ์๋ต)
// 3 2 0
// 3 2 1
// 3 2 2
// 3 2 3
// 3 3 0
// 3 3 1
// 3 3 2
// 3 3 3
ํ๋์ ํจ์์ O(Nยฒ)์ O(N)์ด ํจ๊ฒ ์์ด 'O(Nยฒ)+O(N)'์ผ๋ก ํํํ ์ ์์ ๋, ์๋ฃ๊ฐ ํด ์๋ก O(Nยฒ)์ ์ํฅ์ด ํฌ๋ฏ๋ก O(N)์ ์๋ตํ๊ณ O(Nยฒ)๋ก๋ง ํ๊ธฐํ๋ค.
// ๐ต O(Nยฒ)+O(N) โ O(Nยฒ)
const logItems = (n) => {
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) {
console.log(i, j);
}
}
for (let k = 0; k < n; k++) {
console.log(k);
}
};
logItems(4);
์ซ์๊ฐ ์ผ๋ง๋ ์ปค์ง๋ ํ ๋ฒ์ ์์
๋ง ํ๋ logic์ด๋ค.
e.g. (JavaScript๋ ์๋์ง๋ง) arr.get[3]
: index 3์ ํด๋นํ๋ ์์ ์ฐพ๊ธฐ
constant๋ผ๊ณ ๋ ํ๊ธฐํ๋ค.
๊ฐ์ฅ ๋น ๋ฅด๊ฒ ์ฐ์ฐํ ์ ์๋ค.
ref. arr.push()
, arr.pop()
// ๐ต ํ ๋ฒ๋ง ๊ณ์ฐ
const addItems = (n) => {
return n + n;
};
addItems(4);
๋ค ๊ฐ์ง ์ค O(1) ๋ค์์ผ๋ก ๊ฐ์ฅ ํจ์จ์ ์ด๋ค.
e.g. logโ1,073,741,824๋ฅผ 31ํ๋ง์ ์ฐ์ฐํ ์ ์๋ค.
LinkedList๋ head์ tatil์ pointer๋ก??? ๊ฐ์ง๊ณ ์๋ค??? ๊ทธ๋์ class์ pointer ๊ฐ๋ ์ด ํ์ํ ๊ฑฐ์
๊ฐ์ด 7 ํ๋๋ง ์์ ๋
class Node {
constructor (value) {
this.value = value;
this.next = null;
}
}
class Node {
constructor (value) {
this.value = value;
this.prev = null;
this.next = null;
}
}
class DbLinkedList {
constructor (value) {
const newNode = new Node (Value);
this.head = newNode;
this.tail = this.head;
this.length = 1;
}
}
์ํํธ์จ์ด ์ดํ๋ค์ง๊ธฐ - ์ค๋ฑ - ์๊ฐ ๋ณต์ก๋