[바미] 알고리즘 수업 - 점근적 표기 1

https://www.acmicpc.net/problem/24313

24313번: 알고리즘 수업 - 점근적 표기 1

---

코드

const input = require('fs').readFileSync('/dev/stdin').toString().split('\n');
const n = Number(input[2])
const [a1, a0] = input[0].split(" ").map((a) => Number(a))
const fnSum = a1 * n + a0
const g = Number(input[1])
const gn = g * n

if(a0 <= (g-a1)*n && g >= a1) {
    console.log(1)
} else {
    console.log(0)    
}

 

const input = require('fs').readFileSync('/dev/stdin').toString().split('\n');
const n = Number(input[2])
const [a1, a0] = input[0].split(" ").map((a) => Number(a))
const fnSum = a1 * n + a0
const g = Number(input[1])
const gn = g * n

이 부분에서는 입력을 처리하여 필요한 변수를 초기화 해주고 있습니다. n은 n0로, 주어진 조건에서 f(n)과 c * n을 비교하는 데 사용될 기준점이고, fnSum은 주어진 n에서 f(n)의 값이고, gn은 그 n에서 g(n), 즉 c * n의 값입니다.

if(a0 <= (g-a1)*n && g >= a1) {
    console.log(1)
} else {
    console.log(0)    
}

이 로직의 핵심은 f(n) ≤ c * n 조건을 만족하는지 여부를 판단하는 것인데 조건 a0 <= (g-a1)*n && g >= a1는 f(n)이 c * n에 의해 상한될 수 있는지 확인합니다. 이 조건은 두 부분으로 구성됩니다.

1. g >= a1: 이는 f(n)의 선형 부분이 c * n의 성장률을 초과하지 않음을 보장합니다. 즉, f(n)의 기울기가 c에 의한 기울기를 초과하지 않아야 함을 의미함.
2. a0 <= (g-a1)*n: 이는 n0에서 f(n)과 c * n의 차이가 a0에 의해 상쇄될 수 있음을 보장함.

문제 설명

이 문제는 알고리즘의 시간 복잡도를 점근적으로 분석하는 O-표기법을 이해하고 적용하는 데 있고, O(n)은 어떤 알고리즘의 실행 시간이 입력 크기 n에 선형적으로 비례하는 최악의 경우 시간 복잡도를 나타냅니다. 

 

여기서, f(n) ≤ c * n 조건은 알고리즘의 실행 시간 (f(n))이 어떤 상수 c와 입력 크기 n의 선형 조합에 의해 상한될 수 있음을 나타냅니다.

이 코드는 f(n)이 주어진 조건 하에서 선형 시간 복잡도, 즉 O(n)을 만족하는지를 확인합니다. 

조건 a0 <= (g-a1)*n && g >= a1를 만족하면 f(n)은 주어진 n0 이상에서 모든 n에 대해 c * n으로 상한될 수 있으며, 따라서 O(n)에 속한다고 볼 수 있습니다.

---

다른 풀이

const input = require('fs').readFileSync('/dev/stdin').toString().split('\n');
const [a1, a0] = input[0].split(" ").map(Number); // f(n)의 계수
const c = Number(input[1]); // c 값
const n0 = Number(input[2]); // n0 값

// n >= n0에 대해 f(n)이 c*n보다 작거나 같은지 확인하는 함수
function isOBounded(a1, a0, c, n0) {
    // n0부터 시작하여 몇 가지 값으로 검증
    for (let n = n0; n <= n0 + 100; n++) {
        if (a1 * n + a0 > c * n) {
            return false;
        }
    }
    return true;
}

console.log(isOBounded(a1, a0, c, n0) ? 1 : 0);