시간 복잡도

시간 복잡도는 알고리즘의 성능을 평가하는 척도이다. 데이터 구조나 알고리즘이 얼마나 빠르거나 느린지를 실제 시간이 아닌, 단계(step)로 측정하기에 단계 수가 적을수록 더 효율적인 알고리즘이다. 예를 들어, 선형 탐색(Linear Search)은 O(n)의 시간 복잡도를 가지며, 데이터 양에 비례해 시간이 증가하지만, 이진 탐색(Binary Search)은 O(log n)으로 훨씬 빠르게 작동한다.



비휘발성 메모리와 휘발성 메모리

  • 비휘발성 메모리는 컴퓨터를 껐다 켜도 데이터가 유지되는 메모리.

  • 휘발성 메모리(RAM)는 컴퓨터가 실행 중일 때만 데이터를 저장하는 메모리로, 컴퓨터를 끄면 데이터가 사라진다. RAM은 랜덤 접근(random access)이 가능해 하드 드라이브보다 빠르게 데이터를 읽고 쓸 수 있다.



배열의 메모리 구조

배열을 사용할 때, 컴퓨터는 배열의 크기와 시작 주소를 알고 있어야 한다. 배열은 연속된 메모리 공간을 차지하며, 이를 위해 메모리 공간을 미리 할당해야 한다. 배열을 만들 때 컴퓨터에게 얼마나 큰 배열이 필요한지를 미리 알려주어야 한다. 예를 들어, “이 배열은 4개의 요소를 저장할 수 있어야 한다”는 식으로 요청한다. 이 과정은 자바스크립트나 파이썬에서는 개발자가 선언하지 않는 부분이다.



배열에서의 주요 작업들

1. 읽기 (Reading) : 특정한 위치를 읽음

배열은 0부터 인덱스가 매겨지며, 컴퓨터는 배열의 시작 위치와 길이를 알고 있기 때문에, 특정 인덱스에서 값을 읽어내는 데 시간이 거의 들지 않아 빠르다. 이는 배열의 길이와 무관하게 O(1)의 시간 복잡도를 가진다.


2. 검색 (Searching) : 특정 값을 찾을 때

배열은 랜덤 액세스를 통해 특정 위치로 이동할 수 있지만, 값 자체는 알 수 없기 때문에 하나씩 열어보며 확인해야 한다. 이 작업은 배열의 크기에 따라 O(n)의 시간 복잡도를 가질 수 있다.


3. 삽입 (Insertion) : 배열에 값을 삽입

  • 끝에 삽입하는 것은 배열의 크기와 끝 위치를 알고 있기 때문에 바로 추가할 수 있다. O(1)

  • 중간에 삽입하려면 해당 위치 이후의 모든 요소를 한 칸씩 오른쪽으로 이동해야 하므로 시간이 더 걸린다. O(n)

  • 만약 배열이 가득 차 있다면, 새로운 배열을 만들고 기존 배열을 복사한 후 새 값을 삽입해야 하므로, 추가 시간이 필요하다.


4. 삭제 (Deletion)

배열에서 값을 삭제하면 그 빈 공간을 채우기 위해 이후의 모든 요소를 왼쪽으로 이동시켜야 한다. O(n) 배열이 크면 클수록 이 작업은 더 오래 걸린다.



배열의 장단점

장점: 배열에서 읽기는 매우 빠르며, 항상 O(1)의 성능을 보장한다.

단점: 검색, 삽입, 삭제는 특히 배열의 크기가 클수록 성능이 저하된다. 특히 중간에서 값을 삽입하거나 삭제할 때는 많은 데이터를 이동시켜야 하기 때문에 비효율적일 수 있다.



니꼬쌤 수업 참고