리액트와 시간 복잡도

 최근에 깨달은 점이 있다. 나는 개발을 다소 안일하게 생각하고 있었던 것 같다. 특히 비전공자인 만큼 개념적인 부분에서 더 노력해야 하는데, 지금까지는 포트폴리오를 꾸미는 데에만 집중해 왔다. 그래서 오늘은 시간 복잡도에 대해 공부한 내용을 정리하려고 한다.

시간 복잡도

알고리즘이 수행되는데 걸리는 연산 횟수를 입력 크기 n의 함수로 나타낸 것. 실제 실행 시간이 아니라, 연산 횟수가 입력 크기에 따라 어떻게 증가하는지를 표현한다. 일반적으로 Big-O 표기법을 사용해서 최악의 경우(worst case) 시간복잡도를 나타낸다.

Big-O

증가 속도의 상한선을 수학적으로 표현하는 방식이며, 상수나 작은 항은 무시하고 n의 최고차항만 고려한다.

시간과 입력의 함수 관계라고 하면서 실제로 시간이 아닌 입력 횟수로 표현하는 이유는 프로그래밍 언어에 따라 같은 알고리즘이어도 속도가 달라질 수 있기 때문이라고 한다.

예를 들어 O(nlogn)은 “n번 반복하면서 각 반복마다 logn의 연산을 수행” 혹은 “logn번 반복하면서 각 반복마다 n의 연산을 수행”으로 해석할 수 있다.

그리고 log의 밑 같은 경우, Big-O에서는 상수 차이는 무시되므로 O(logn)이면 밑이 무엇이든 동일하게 취급한다.

O(1)은 정말 1번 연산이 아닌, 입력 크기와 무관하게 항상 일정한 횟수라는 의미이다.

질문 받은 주제는 다음과 같았다.

import { useState, useEffect } from 'react';

export default function UserList() {
  const [users, setUsers] = useState([]);

  useEffect(() => {
    fetch('/api/users')
      .then(res => res.json()
      .then(body => setUsers(body));
  }, []);

  return (
    <div>
      {users.map(user => (
        <p key={user.id}>{user.name}</p>
      ))}
    </div>
  );
}

 이 화면은 마운트 시 useEffect 내 함수가 한 번 실행되어 users를 불러온다. users의 state가 변경되면 컴포넌트가 재렌더링된다. 이 과정에서 React는 이전 VDOM과 새 VDOM을 key 기반으로 O(n)에 비교하고, 변경된 항목만 O(m)으로 실제 DOM에 반영한다. 초기에는 m≈n이므로 전체적으로 선형 시간 복잡도를 가진다.

  (1) 마운트 시점 - useEffect는 1회 호출 useEffect의 의존성 배열이 빈 배열이므로, 이 이펙트는 컴포넌트가 처음 마운트될 때 딱 한번만 실행된다. 초기 렌더 때 users는 빈 배열이므로, 화면에는 <div></div> 만 렌더링된다.

(2) 데이터 패칭 - state 업데이트 -> 재렌더 마운트 직후 이펙트가 실행되어 /api/users를 fetch 하고, 응답을 res.json()으로 파싱한 뒤 setUsers(body)가 호출된다. 이 때 users의 state가 변경되므로 React는 화면을 재렌더링한다.

(3) React의 DOM 비교: “이전 VDOM vs 새 VDOM” 재렌더에서는 새 JSX로부터 새로운 가상 DOM이 만들어진다. React는 이전 가상 DOM과 새 가상 DOM을 비교(diff)하면서 “무엇이 바뀌었는지”를 계산한다.

이 때 비교를 위해 key={user.id}를 사용하는데, 이는 매우 중요하다. React는 같은 key를 가진 노드는 같은 항목으로 간주하여 기존 노드를 재사용하고, 필요한 속성만 업데이트한다.

이전 DOM에는 없고 새 DOM에만 있는 key는 삽입, 새 DOM에는 없고 이전에만 있었던 key는 삭제로 처리한다.

순서가 바뀌어도 key로 동일 여부를 판단하기 때문에 불필요한 재마운트를 크게 줄인다.

(4) Commit 단계 - 변경분만 실제 DOM에 반영 이전/새 VDOM 비교 결과로 만들어진 “변경 작업 목록(effect list)”를 바탕으로, React는 Commit 단계에서 변경된 부분만 실제 DOM에 반영한다. 초기에 빈 배열 -> N개의

로 바뀌는 첫 업데이트에서는, 실제 DOM에

가 N개 삽입된다. 이후 users가 바뀌지 않으면, 이펙트는 다시 실행되지 않고 DOM도 바뀌지 않는다.

시간 복잡도 분석

리스트 길이를 n, 실제로 DOM에서 바뀌는 항목 수를 m이라고 가정한다. 일반적인 경우, m ≤ n 이다.

1. Render 단계 새 VDOM 생성, 이전 VDOM vs 새 VDOM 비교(diff), key 매칭 등 같은 단계의 children 리스트를 선형으로 순회하며 비교하므로 O(n)에 수렴.

2. Commit 단계 실제 DOM에 변경 항목만 반영 (삽입/갱신/삭제) 변경된 항목 수를 m이라 하면 O(m)

3. 초기 빈 배열 -> n개 추가되는 첫 업데이트 m ≈ n 이라서 Commit도 O(n) 따라서 초기 업데이트는 O(n) + O(n) ≈ O(n)로 볼 수 있다.

최근에 개발 면접에서 내가 놓치고 있던 것들을 캐치할 수 있어서 좋았다. 이를 토대로 좀 더 개발 지식을 다져야겠다.