약수의 갯수와 덧셈

나의 풀이

근데 약수를 어떻게 구하지? for문 돌려야하나?...
예전에 for문 넣었다가 $O(N^2)$ 복잡도가 나와버려서 왠지 하기 싫지만 방법이 떠오르지 않음으로 일단 만들어야겠다.

function sol0(left, right) {
    var answer = 0;

    for (let i = left ; i <= right ; i++ ){
        var divisor = -1
        for ( let j = 1 ; j < i ; j++){
            if (i%j === 0) {
                divisor *= -1
            }
        }
        answer += i*divisor
    }

    return answer;
}

내가 짠 코드의 시간 복잡도를 계산해보자
for문안에 n짜리 for문이 있으니 $n^2$일 것이다.

다른 사람의 풀이

//  다른 사람의 풀이 1
function sol1(left, right) {
    var answer = 0;
    for (let i = left; i <= right; i++) {
        if (Number.isInteger(Math.sqrt(i))) {
            answer -= i;
        } else {
            answer += i;
        }
    }
    return answer;
}

제곱근이 정수면 약수의 갯수가 홀수인것을 이용한 방법이다.
시간 복잡도가 N일테니 무조건 나보다 빠를 것이다.

참조 : [노트] 모든 약수를 구하는 알고리즘은 O(sqrt(n))이다.

//  다른 사람의 풀이 2
function sol2(left, right) {
    let sum = (left+right)/2*(right-left+1);
    let l = Math.ceil(Math.sqrt(left));
    while (l**2 <= right) sum -= (l++**2)*2
    return sum
}

sum 우선 모든 수를 더한다.
l 제곱근중 가장 작은 정수를 찾는다.
while l을 증가시켜가며 2배값을 뺀다(홀수인 수가 이미 더해져있기때문에)

속도 비교

속도는 1,2 > 0 일 것이다. 시간 복잡도에서 한 차원의 차이가 나서 어쩔 수 없을 것이다.

그리고 오늘의 속도 비교에서는 두가지를 볼것이다.

1. 1천만회에서 1만회로 부하량 저하
   이유는 결과가 나오는 시간이 너무 오래 걸리기 때문이다.
2. 처리할 데이터 범위를 10 / 50 / 100배 차이로 변경하기
   이유는 시간 복잡도가 $O(N)$ 인 경우와 $O(N^2)$ 인 경우를 좀더 자세히 보기 위해서다.

아래와 같은 방식으로 진행하였다.

// 솔루션0
function sol0(left, right) {
  var answer = 0;

  for (let i = left; i <= right; i++) {
    var divisor = -1;
    for (let j = 1; j < i; j++) {
      if (i % j === 0) {
        divisor *= -1;
      }
    }
    answer += i * divisor;
  }

  return answer;
}

// 솔루션1
function sol1(left, right) {
  var answer = 0;
  for (let i = left; i <= right; i++) {
    if (Number.isInteger(Math.sqrt(i))) {
      answer -= i;
    } else {
      answer += i;
    }
  }
  return answer;
}

// 솔루션2
function sol2(left, right) {
  let sum = ((left + right) / 2) * (right - left + 1);
  let l = Math.ceil(Math.sqrt(left));
  while (l ** 2 <= right) sum -= (l++) ** 2 * 2;
  return sum;
}

//////////////////////////////////////////////////////////

async function runSolutionWithTiming(solutionFn, a, b) {
  const startTime = new Date();
  for (let i = 0; i < 10000000; i++) {
    await solutionFn(a, b);
  }
  const endTime = new Date();
  const executionTime = endTime - startTime;

  console.log(`${solutionFn.name} 실행 시간: ${executionTime}ms`);
}

async function main() {
  const a = 1;
  const b = 10;

  await runSolutionWithTiming(sol0, a, b);

  await runSolutionWithTiming(sol1, a, b);
  await runSolutionWithTiming(sol2, a, b);
}

main()
  .then(() => {
    console.log("모든 실행이 완료되었습니다.");
  })
  .catch((error) => {
    console.error("에러 발생:", error);
  });

1천만회 / 10자리

1만회 / 10자리

너무 짧게 줄어들었다. 반복횟수는 그때그때 조절해야겠다.

100만회 / 10자리

반복 횟수를 0하나 떼니까 정직하게 작동시간도 0하나가 빠졌다.

이하 작동의 결과는 한번에 정리해서 보여주겠다.

속도 변화 해석

1. 반복 횟수가 10% 줄어들면 실행 시간도 10% 줄어든다.
   하지만 1000배 줄어든다고 시간이 1000배 줄지는 않는다.
   아마 고정적으로 소모되는 어떤 시간이 있어서 일정량 이하로는 떨어지지 않는듯하다.
2. 시간복잡도가 $O(N^2)$정도만 되어도 시간이 미친듯이 널뛰기한다.
   그러므로 시간 복잡도는 무조건 작게 만들어야한다.

공부하며 느낀 점

1. 반복 횟수와 작동 시간은 정비례한다.
   하지만 작동 횟수가 충분히 많아야한다.
2. 제곱이라는 것은 정말 무서움을 알게 되었다.
   정말 작은 범위의 부하를 걸었을 뿐인인데 복잡도가 $N^2$인 경우에는 시간이 1600배 가량 증가해버려서 30분 이상 걸리기도한다.
3. 시간 복잡도가 log나 지수가 1보다 작은 제곱수일수도 있다. 이경우에는 부하가 높아져도 속도가 크게 늘지 않는다. 가능하다면 이런 복잡도를 가지도록 유도해야겠다.
4. 수학을 잘알아야 효율적으로 코드를 짤 수 있다.

참조한 페이지

[노트] 모든 약수를 구하는 알고리즘은 O(sqrt(n))이다.