StudyData Structure

동적 배열 vs 연결 리스트

동적 배열(Dynamic array) vs 연결 리스트(Linked list)

  1. 동적 배열(Dynamic array)
  • 장점 : search - O(1) = Indexing
  • 단점 : insert, delete - O(n)

  • python의 동적배열은 list이다.

    • append, pop - O(1)
      1
      2
      3
      4
      5
      6
      7
      8
      9
      다음과 같이 이미 할당된 배열의 공간이 있을 경우

      ex) [a][b][c][d][ ][ ][ ][ ]

      append(e)를 하게되면 d의 바로 뒤에 붙게 되고
      pop을 해도 바로 뒤에서 빼기 때문에 O(1)이다.

      그런데 a의 앞에 e를 넣으려고 하면 d부터 데이터를 한칸씩 밀어야한다.
      있는 데이터만큼 옮겨야 하기 때문에 O(n)이다.

  • 메모리가 붙어 있기 때문에 cache hit가 존재한다.

  • 메모리를 가져올 때 통째로 그 주변까지 가져온다.
  1. 연결 리스트(Linked list)
  • 장점 : insert, delete - O(1)
    • head와 tail만 이어주는 두번의 작업으로 끝난다.
    • delete의 경우 한번의 작업으로 끝나고 아무것도 연결이 되지 않은 데이터는 가비지컬렉터에 의해 사라진다.
  • 단점 : search - O(n)
    • 데이터를 찾을 때 데이터의 개수만큼 if으로 찾아야 한다.

BST(Binary Search Tree)

  • insert, delete, search - O(log(n)) = 3가지 모두 성능이 좋음

  • height of tree -> 아무리 많이 비교해도 트리의 높이만큼만 비교하게 된다.(log(n))

  • 데이터는 다른 곳에 저장되어 있고 tree 구조로 search만 한다.

  • 실제 데이터와 포인터로 연결되어 있기 때문에 접근가능하다.

분할 상환 분석(Amortized Analysis)

  • 평균적으로 실행시간이 얼마나 걸리는지 측정하는 방법

  • 동적 배열(DA)의 예

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    1) 배열이 다 찼을 경우, 배열의 크기를 2배로 늘림(Array Doubling)
    2) 공간을 할당할 경우 = O(n)
    3) 공간을 할당한 상태에서 데이터를 넣을 경우 = O(1)

    ex)
    [a] x 2 = [a][ ] : O(n)
    [a][ ] = [a][b] : O(1)

    [a][b] x 2 = [a][b][ ][ ] : O(n)
    [a][b][ ][ ] = [a][b][c][d] : O(1)

    [a][b][c][d] x 2 = [a][b][c][d][ ][ ][ ][ ] : O(n)
    [a][b][c][d][ ][ ][ ][ ] = [a][b][c][d][e][f][g][h] : O(1)

    4) 수가 늘어날수록 O(n)보다 O(1)이 더 자주 일어나게 됨

  • 어떤 특정 상황에서는 최악의 경우이지만 나머지 상황에서는 좋은 결과를 보여줌

Share