• 카테고리

    질문 & 답변
  • 세부 분야

    알고리즘 · 자료구조

  • 해결 여부

    미해결

빅오 시간 복잡도 알려주세요!!!!!!

22.12.23 18:14 작성 조회수 290

0

function solution(scores) {
  let scoreGroup = {};
  let result = [];

  scores.forEach((score, i) => {
    if (scoreGroup[score] === undefined) {
      scoreGroup[score] = [];
    }
    scoreGroup[score].push(i);
  });

  let rank = scores.length;

// 아래 부분 시간 복잡도 질문합니다.
  Object.keys(scoreGroup).forEach((key) => {
    rank -= scoreGroup[key].length - 1;

    scoreGroup[key].forEach((index) => {
      result[index] = rank;
    });

    rank -= 1;
  });

  return result;
}

제가 짠 코드는 다음과 같습니다.

Q) 여기서 이 부분 시간 복잡도가 O(n)인가요 O(n^2)인가요??

Object.keys(scoreGroup).forEach((key) => {
    rank -= scoreGroup[key].length - 1;

    scoreGroup[key].forEach((index) => {
      result[index] = rank;
    });

    rank -= 1;
  });

forEach가 이중으로 실행되지만 key가 n개면 각 value 길이는 1이 되고, key가 1개이면 각 value 길이가 n이 되는 상황이라서 O(n)인거 같은데... 정확하게 알려주시면 감사하겠습니다😭

 

답변 1

답변을 작성해보세요.

0

안녕하세요^^

시간복잡도는 중첩 for 문이라도 안쪽 for문이 반복하는 횟수가 시간복잡도를 결정합니다.

결국 result[index] = rank; 연산을 몇 번 했는가가 중요합니다.

O(n)으로 보여집니다.