프로그래머스 - 내적
공부하며 느낀 점

내적

나의 풀이

무난하게 for문을 돌려야할것같다.

function sol0(a, b) {
    var answer = 0;
    const length = a.length

    for (let i = 0 ; i < length ; i++) {
        answer += a[i]*b[i]
    }

    return answer;
}

다른 사람의 풀이

// 다른 사람의 풀이 1
function sol1(a, b) {
    return a.reduce((acc, _, i) => acc += a[i] * b[i], 0);
}

reduce((acc, _, i) 의 _는 사용하지 않는 인자의 경우 넣는 것이라고한다.

좀더 이해하기 쉽게 적은건 아래 버전같다

// 다른 사람의 풀이 11
function sol11(a, b) {
    return a.reduce((acc, val, i) => acc + val * b[i], 0);
}

// 다른 사람의 풀이 21
function sol21(a, b) {
   return a.map((a,i)=> a*b[i]).reduce((acc,val)=>{
        return acc+val
    },0)
}

// 다른 사람의 풀이 22
function sol22(a, b) {
    return [...Array(a.length)].map((e, i) => a[i]*b[i]).reduce((a, e) => a+e);
}

같은 방법인데 맵을 사용한사람과 거기에 펼침 연산자까지 사용한 사람의 예시다.

속도 비교

어제의 교훈으로 단순히 부하를 늘리는게 아니라 시간 복잡도를 봐야하는걸 알았다.

sol0 : 곱하기는 복잡도가 1이고 그것을 n회 반복함으로 O(N)의 복잡도를 가진다.

sol1 : 마찬가지의 이유로 O(N)이다.

sol21 : map은 n, reduce는 n이지만 n*n이 아닌 n+n이므로 O(N)이다.

sol22 : 역시 n+n+n이므로 시간복잡도는 O(N)이다.

실제로 돌려보자

// 솔루션0
// 솔루션0
function sol0(a, b) {
  var answer = 0;
  const length = a.length;

  for (let i = 0; i < length; i++) {
    answer += a[i] * b[i];
  }

  return answer;
}

// 솔루션1
function sol1(a, b) {
  return a.reduce((acc, _, i) => (acc += a[i] * b[i]), 0);
}

function sol11(a, b) {
  return a.reduce((acc, val, i) => acc + val * b[i], 0);
}

// 솔루션2
function sol21(a, b) {
  return a
    .map((a, i) => a * b[i])
    .reduce((acc, val) => {
      return acc + val;
    }, 0);
}

function sol22(a, b) {
  return [...Array(a.length)]
    .map((e, i) => a[i] * b[i])
    .reduce((a, e) => a + e);
}

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

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() {
  function generateNumberArray(n, isAscending = true) {
    if (isAscending) {
      return Array.from({ length: n + 1 }, (_, i) => i);
    } else {
      return Array.from({ length: n + 1 }, (_, i) => n - i);
    }
  }

  const a = generateNumberArray(100); // 0부터 100까지 오름차순 배열
  const b = generateNumberArray(100, false); // 100부터 0까지 내림차순 배열

  await runSolutionWithTiming(sol0, a, b);

  await runSolutionWithTiming(sol1, a, b);
  await runSolutionWithTiming(sol11, a, b);

  await runSolutionWithTiming(sol21, a, b);
  await runSolutionWithTiming(sol22, a, b);
}

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

위와같이 100의 자리를 넣고 해보면 아래와 같은 결과가 나온다.

예상대로 펼침 연산자나 map을 사용하면 더 느리다.
그리고 1과 11은 거의 똑같은데 11이 더 빠른걸 보니, 같은 형식이라도 약간의 차이로 속도가 갈리는것같다.

이제 부하를 10배로 늘려보자, O(N)의 시간 복잡도를 가지니 모두 같은 수준으로 시간이 증가할 것이다.

정확히 10배 증가하지는 않았다.

시간 복잡도 해설

증가 수치는 들쭉날쭉이고 배율로 봤을때 7.67배가 증가했다.

시간 복잡도가 O(N) 이라는것은 입력이 10배 늘어나시, 시간이 "최대" 10배 증가할 것이로 "예측"이 된다는 것이지 "항상" 10배가 된다는 의미는 아니다.

그러므로 10배가 안나오는 것은 당연하다고 판단된다.

공부하며 느낀 점

1. 시간 복잡도는 어디까지나 기대값이지 절대적인 지표가 아님을 알게되었다.
   공부만해서는 쓸 수 가 없고 이렇게 실제로 봐야지 알 수 있는것같다.

2. 겉보기에는 시간 복잡도가 높을 것같아도 실제로는 곱해지는게 아니라 더해지는 경우에는 시간 복잡도가 똑같다.

3. 시간복잡도가 똑같이 O(N) 이면 비슷한 비율로 실행 속도가 증가한다.
   즉, 시간 복잡도가 같더라도, 낮은 부하일때 속도가 빠른것이 높은 부하일때도 속도가 빠르다.