Array·Vector·시간복잡도

이 Part에서 다루는 것

• 고정 배열(Array)과 동적 배열(Vector)의 구현 관점 차이
• 벡터의 증설(reallocation)과 size/capacity 관계
• Big-O를 읽는 방법과 실전에서 자주 쓰는 복잡도
• 벡터 vs 리스트 연산 복잡도 비교

학습 목표

• push_back이 왜 “항상” O(1)이 아니라 “암화(amortized) O(1)”인지 설명할 수 있다.
• reserve, clear가 내부 상태(size, capacity)에 주는 영향을 설명할 수 있다.
• 요구사항(임의 접근/중간 삽입/메모리 지역성)에 맞춰 벡터와 리스트를 구분해 선택할 수 있다.

---

Array 클래스 구현 (고정 용량)

핵심 멤버

변수	의미
_buffer	실제 데이터 저장 메모리
_size	현재 사용 원소 수
_capacity	총 용량(고정)

핵심 포인트:

• 고정 용량에서는 push_back 시 용량 초과를 허용하지 않음
• 인덱스 접근은 빠르지만(O(1)), 용량 변경은 불가
• 생성자에 explicit을 붙여 암시적 변환 실수 방지

#pragma once
#include <assert.h>

class Array {
    using T = int;

public:
    explicit Array(int capacity = 100) : _capacity(capacity)
    {
        _buffer = new T[_capacity];
    }

    ~Array()
    {
        delete[] _buffer;
    }

    void push_back(const T& data)
    {
        if (_size == _capacity)
            return;

        _buffer[_size++] = data;
    }

    T& operator[](int index)
    {
        assert(index >= 0 && index < _size);
        return _buffer[index];
    }

    int size() const { return _size; }
    int capacity() const { return _capacity; }

private:
    T* _buffer = nullptr;
    int _size = 0;
    int _capacity = 0;
};

---

Vector 클래스 구현 (가변 용량)

Array와의 본질적 차이

• 꽉 차면 더 큰 공간을 다시 할당해서 옮긴다(reallocation).
• 이 과정에서 “복사 비용”이 한번 크게 발생할 수 있다.

push_back 내부 흐름

1. _size == _capacity면 증설 기준 계산
2. reserve(newCapacity) 호출
3. 새 데이터 기록 후 _size++

reserve 예시

void reserve(int capacity)
{
    if (_capacity >= capacity)
        return;

    T* newData = new T[capacity];
    for (int i = 0; i < _size; ++i)
        newData[i] = _buffer[i];

    delete[] _buffer;
    _buffer = newData;
    _capacity = capacity;
}

clear의 의미

• clear()는 보통 _size만 0으로 만들고
• _capacity는 유지해 이후 재사용 성능을 확보

---

시간 복잡도(Big-O) 핵심

왜 쓰나

• 환경(PC, 컴파일러, 입력 분포)에 따라 절대 시간은 달라지므로
• 입력 크기 N이 커질 때 성능이 어떻게 늘어나는지 “성장률”로 비교

읽는 법

1. 지배항만 남긴다
2. 상수/낮은 차수 항은 생략한다
3. 최악/평균/암화 상황을 문맥에 맞게 구분한다

복잡도	의미	예시
O(1)	입력 크기와 무관	배열 인덱스 접근
O(log N)	반씩 줄어듦	이진 탐색
O(N)	한 번 순회	선형 탐색
O(N log N)	효율적 정렬 대다수	Merge/Heap sort
O(N²)	이중 순회	단순 이중 루프 정렬

주의:

• N이 커지면 O(N²) 이상은 빠르게 병목이 됩니다.

---

벡터 vs 리스트 복잡도 비교

벡터(동적 배열)

작업	시간 복잡도	비고
끝 삽입 push_back	평균 O(1), 드물게 O(N)	재할당 시 복사 비용
시작/중간 삽입	O(N)	뒤 원소 이동
끝 삭제 pop_back	O(1)
시작/중간 삭제	O(N)	뒤 원소 이동
임의 접근 []	O(1)	연속 메모리

연결 리스트

작업	시간 복잡도	비고
삽입/삭제(위치 노드 알고 있음)	O(1)	링크 변경만 수행
인덱스로 위치 찾기	O(N)	순회 필요
임의 접근	O(N)	연속 메모리 아님

결론(실전 선택)

• 임의 접근/순회/캐시 친화성이 중요하면 벡터 우선
• 이미 노드를 잡고 있는 상태에서 삽입/삭제가 잦다면 리스트 검토
• “리스트는 삽입/삭제가 빠르다”는 문장은 위치 노드가 이미 있을 때만 정확하다

체크 질문 (스스로 답해보기)

• push_back의 O(1)과 재할당 O(N)은 왜 모순이 아닌가?
• clear() 후에도 capacity를 유지하는 이유는?
• “중간 삭제가 많다”는 말만으로 리스트를 바로 선택하면 위험한 이유는?

---