Ordered Data Structures # WEEK 1 - Run Time Analysis / Array and List Operation

1.3 Run Time Analysis

 

런타임 분석은 입력 데이터의 크기를 늘려가며 어떤 알고리즘이 빠른지 분석하는 기법.

배열의 사이즈를 재조정하는 방법 2가지를 비교해보았음.

• Run-Time Analysis allows us to formalize a method of comparing the speed of an algorithm as the size of input grows.
• We summeraize the runtime in "Big-O notation", leaving only the term that dominates the growth
  • O(1), constant time
    • approximately same time no matter how many data.
  • O(n), linear time
    • as data size grows, running time grows at the same rate
  • O(n^2), polynomial time (다항식 시간)
    • strategy#1 같은 것? O(1), O(n)보다 훨씬 느림

Objective: Access a given index.

• Array의 경우 : just one multiplication no matter how many data in array
  • 데이터의 사이즈 * 인덱스를 더해주면 됨
• List의 경우 : 99 에 접근하고자 하면 move 99 times following next pointer.
  • as the data grows access time grows 
   

Array Resize Strategy

Objective : Resize an array

• Strategy #1 : When the array is full, add two to the capacity
  • actually add up the total number of copies that it takes over the entirety of the algorithm expanding from an initial array of capacity two, all the way down to the when the array is the capacity of two times r.

• Strategy #2 : When the array is full, double the capacity
  • Only once every so often do we have to actually then copy over all the data and move forward. But then we can insert all of that data again before we have to do another copy operation
  • 실제로 복사가 일어나는 횟수가 strategy1에 비해 훨씬 감소함

 

*Amortized running time (할부 시간, 분할 시간 등) : 입력이 같은 빈도로 발생한다는 가정 하에 복잡도를 계산

---

1.4 Array and List Operations

 

Arrays and Lists are both ordered collections of data. There are several key operations common to both all ordered collections that are worth analyzing.

 

Access a Given Index & Insert element at the front

Objective: Access a given index in the collection

 

Find Data

Find Data in Sorted Array

배열에서 중간부터 탐색하면, 세 번의 연산으로 가능하고, 데이터의 절반은 완전히 제거할 수 있음

 

Binary Search! sort하고 중간과 비교 또 중간과 비교 이런 식인가봄.

리스트는 중간으로 바로 가는 매직 포인터는 없으므로 처음부터 다 탐색해야함.

 

Insert After

Objective: Given an element (ListNode or Index), insert a new element immediately afterwords.

 

Arrays and lists are both ordered collections that have complex tradeoffs(절충점) between run-time and flexibilty.

빠르게 실행해야하는지, 어떤 연산을 할지에 따라 Array를 쓸지 list를 쓸지 고민해야한다.

 

We will building data structures using these primitive structures.

프로그래밍을 건축에 비유한다면 데이터 구조들은 일종의 벽돌, 그리고 설계가 디자인기법 등이 되려나.