-
[λ°±μ€] 24262λ²: μκ³ λ¦¬μ¦ μμ - μκ³ λ¦¬μ¦μ μν μκ° 1 (Node.js)π μκ³ λ¦¬μ¦/λ°±μ€ 2024. 9. 9. 11:19
μ κ·Όλ°©μ
μκ³ λ¦¬μ¦μ μκ° λ³΅μ‘λμ λν΄ λ€λ£¨λ κΈ°μ΄λ¬Έμ μ΄λ©° μ μλ μ½λμ μκ°λ³΅μ‘λλ₯Ό λΆμνλ λ¬Έμ μ λλ€.
μ΄ λ¬Έμ λ₯Ό νκΈ° μν΄μ κΈ°λ³Έμ μΌλ‘ μμλμ μΌ ν κ²μ΄ 2κ°μ§κ° μλλ°,
μκ°λ³΅μ‘λμ Big-O νκΈ°λ²μ λλ€.
1. μκ°λ³΅μ‘λ
μκ³ λ¦¬μ¦μ΄ μΌλ§λ 빨리 μ€νλλμ§λ₯Ό μΈ‘μ νλ κΈ°μ€μ λλ€.
μ¦, μ λ ₯μ ν¬κΈ°(λ°μ΄ν° μ)κ° μ»€μ§λ©΄ μκ³ λ¦¬μ¦μ΄ μΌλ§λ λ λ§μ μκ°μ νμλ‘ νλμ§λ₯Ό 보λ κ²μ λλ€.
μλ₯Ό λ€μ΄
let sum = 0; for(let i=0; i<n; i++) { sum += arr[i]; }
n = 3 μ΄λ©΄ 3κ°μ μ«μλ₯Ό λν΄μΌ νλ―λ‘ μ°μ°μ΄ 3λ² μΌμ΄λ©λλ€.
n = 1000μ΄λΌλ©΄ 1000κ°μ μ«μλ₯Ό λν΄μΌ νλ―λ‘ μ°μ°μ΄ 1000λ² μΌμ΄λ©λλ€.
μ¦, λ°°μ΄μ ν¬κΈ°μ λΉλ‘ν΄μ μ°μ° νμλ λμ΄λ©λλ€.
κ²°κ΅ λ°°μ΄μ ν©μ ꡬν λ, λ°°μ΄μ ν¬κΈ°κ° 컀μ§μλ‘ λ λ§μ μκ°μ΄ 걸리λλ°,
μ΄ κ³Όμ μμ μκ° λ³΅μ‘λλ O(n)μ΄λ©°, μ λ ₯ ν¬κΈ° nμ λΉλ‘ν΄μ μκ°μ΄ κ±Έλ¦°λ€λ μλ―Έλ₯Ό κ°μ§κ³ μμ΅λλ€.
2. Big - O νκΈ°λ²
Big-O νκΈ°λ²μ μκ°λ³΅μ‘λλ₯Ό νννλ λ°©λ² μ€ νλλ‘, μκ³ λ¦¬μ¦μ μ±λ₯μ μ λ ₯ ν¬κΈ° nμ λν
ν¨μλ‘ λνλ λλ€. Big-Oλ μ λ ₯ ν¬κΈ°κ° λ§€μ° ν΄ λ, μ¦ nμ΄ λ¬΄νλλ‘ μ»€μ§ λ μκ°λ³΅μ‘λκ°
μ΄λ»κ² λ³νλμ§ λνλ λλ€.
- O(1) : μ λ ₯ ν¬κΈ°μ μκ΄μμ΄ νμ μΌμ ν μκ°.
- O(n) : μ λ ₯ ν¬κΈ°μ λΉλ‘ν΄μ μκ°μ΄ λμ΄λλ κ²½μ°.
- O(n^2) : μ λ ₯ ν¬κΈ°μ λ°λΌ μκ°μ΄ κΈκ²©ν λμ΄λλ κ²½μ°
κ·Έ μΈμλ λ‘κ·Έ μκ° λ³΅μ‘λ, μ ν λ‘κ·Έ μκ°, μ§μ μκ°, ν©ν λ¦¬μΌ μκ° λ±λ±μ΄ λ§μ§λ§ μ¬κΈ°μμ
μ 3κ°λ§ λ€λ€λ³΄μμ΅λλ€.π
μμ: O(1)
let a = 0;
μ΄ μ½λλ μ λ ₯ ν¬κΈ°μ μκ΄μμ΄ λ¨ νλ²μ μ°μ°μΌλ‘ λλκ²λ©λλ€.μ λ ₯ ν¬κΈ°κ° μ무리 μ»€μ Έλ μ΄ μμ μλ νμ μΌμ ν μκ°μ΄ 걸리λ―λ‘ O(1) μ λλ€.
μμ: O(n)
for (int i = 0; i < n; i++) { if (arr[i] == target) { return i; } }
μ΄ μ½λλ λ°°μ΄ μ 체λ₯Ό νμν΄μΌ νλ―λ‘ μκ° λ³΅μ‘λλ O(n)μ λλ€.
μμ: O(n^2)
for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { } }
μ΄ μ½λλ λ κ°μ μ΄μ€ 루νκ° μκΈ° λλ¬Έμ μκ° λ³΅μ‘λλ O(n^2)μ λλ€.
νμ΄ β°
const readline = require("readline"); const rl = readline.createInterface({ input: process.stdin, output: process.stdout, }); let input = []; rl.on("line", function (line) { input.push(line); }).on("close", function () { // MenOfPassion(A[], n) { // i = ⌊n / 2⌋; // return A[i]; # μ½λ1 // } // ν¨μμ μκ° λ³΅μ‘λκ° μμ μκ°μ΄λ―λ‘ 1μ μΆλ ₯ console.log(1); // λ€νμμ μ΅κ³ μ°¨ν μ°¨μλ 0μ΄λ―λ‘ 0μ μΆλ ₯ console.log(0); });
λ°±μ€ 24262λ² λ§ν¬
'π μκ³ λ¦¬μ¦ > λ°±μ€' μΉ΄ν κ³ λ¦¬μ λ€λ₯Έ κΈ
[λ°±μ€] 24264λ²: μκ³ λ¦¬μ¦ μμ - μκ³ λ¦¬μ¦μ μν μκ° 3 (Node.js) (0) 2024.09.09 [λ°±μ€] 24263λ²: μκ³ λ¦¬μ¦ μμ - μκ³ λ¦¬μ¦μ μν μκ° 2 (Node.js) (0) 2024.09.09 [λ°±μ€] 11659λ²: κ΅¬κ° ν© κ΅¬νκΈ° 4 (Node.js) (0) 2024.09.05 [λ°±μ€] 5430λ²: AC (Node.js) (0) 2024.09.04 [λ°±μ€] 2776λ²: μκΈ°μ (Node.js) (0) 2024.09.03