[MIT 6.006 - Introduction to Algorithms ] 2. Data Structure and Dynamic Arrays

 

 

 

 

** Big O notation => 

O(1) : constant time / O(n) : linear time

 

 

 

 

 

 [ Interface vs Data Structure ]

 

Interface : 

- specification

- what data can store

- what operations are supported what they mean

- problem

 

 

Data structure:

- representation

- how to store data

- algorithms to support operations

- solution

 

 

 

2 main interfaces :

set / sequence

 

 

 

2 main Data Structure approaches : 

arrays / pointer-based

 

 

* Static sequence interface:

maintain a sequence of items X0, X1,....., Xn-1 subject to these operations: 

- build(x) : make new DS for items in X

-len() : return n

- iter_seg(): output X0,X1,...,Xn-1 in sequence oreder

- get_at(i) : return Xi (index i)

- set_at(i,x) : set Xi to X

- get_first/last()

-set_fisrt/last(x)

 

 

 

--> Solution(natural) : Static array

- constant time per get_at / set_at / len

- linear time per build / iter_seg

Memory allocation model: allocate array of size n in linear time.

=> space use <= time (almost same)

 

 

 

 

 

key) word RAM model of computation

- memory= array of w-bit words 

- "array" = consecutive chunk of memory

=> array[i] = memory[address(array) + i]

=> array access is constant time

 

Assume w > = log n

 

 

 

Dynamic sequence interface:

static sequence, plus;

 - insert_at(i,x) : make x the new Xi,  shifting Xi -> X1+1->Xi+2 -> ..... -> Xn-1 

-delete_at(i) : shift  Xi -> X1+1<-Xi+2 <- ..... <- Xn-1

insert/delete_first/ last(x)/()

 

 

 

 

* Linked Lists : 

 

store items in a bunch of notes, each note has item-unit/next unit

 

 

 

Dynamic sequence operations

< Static Array >

-> insert/ delete_at() cost

linear time

1) shifting

2)allocation / copying

 

< Linked Lists>

-> insert/delete- first() : constanct time 

 

 

 

 

Dynamic arrays (Python Lists) 

 

 - relax constaraint size(array) = n <-- # item in sequence

-enforce sizze of array  = 0(n)

- maintain A[i]=Xi

- insert_last(x) : add to end unless n = size

 

 

 

- if n= size : allocate new array of 2 * size

- n insert_last() from empty array

resize at n = 1,2,4,8,16,....(doubling)

=> resize cost = O(1+2+4+8+16+...)

= O(Σ2^i) = 2^(k+1) - 1 = O(2^logn) = O(n)

 

 

Amortization

: operation takes T(n) amortized time if any k operations take <= k*T(n) time

( averaging over operation sequence ) 

 

 

&nbsp;( 1 - costant time / n - linear time )