1byte = 8 bit
1MB = 1024byte = 2^10 bit
1KB = 1024 MB = 2^10*2^10 = 2^20
1GB = 1024 KB = 2^10*2^10 = 2^30
4GB = 2^30*2^2 = 2^32
1TB = 2^40
➤ Unary & Binary operator
Unary: 没几个, &(地址)，*(pointer ref), !,~(complement) ,+(positive),-(negation),++,--
Binary: logical,math operators: &(bitwise and),&&(logical and), +(add), - (minus)...
➤ Array
contiguous memory allocated for array so no growth
➤ HashTable - array with hash function
function take key to hash value for mapping index in hashtable
and store key
*make use all info provided by key
*uniformly distribute output across table
*map similar keys to very different hash values
deal with collections(avoid by good hash function)
-linear probing
assign to next available slot
* increase loop up time to O(N)
* increase chance of collision - clustering
-sepearate chaining
array points to linked list
* search O(n/k) - k lists n keys, distribute evenly
➤ Graph
BFS:Time O(V+E), Space O(V) - tree or known, O(V+E) - adjacency list, O(V^2) - adjacency matrix
DFS: Time O(V+E), Space O(V) - worst case all vertices in path to store in the stack
Applications：
1.social network (union find)
2.city road
3.precedence constraint(topological sort)
Adjacency Matrix: v*v
--diagnal 0 means no itself loop
--symetric only in undriected graph
Pros:
*easy implement
*remove is O(1)
*O(1) to check for specific edge
Cons:
!O(v^2)more space
!adding vertex cause O(v^2), rewrite all list.
Adjacency list --java ArrayList<List<Integer>> eg: [0][1,2,3]
-- use linkedlist
Pros
*O(v+E)spaces, worst case O(v^2)
*Adding vertex is easirer
Cons
!Query of specified edge takes O(v)
➤Other
"The idea behind bidirectional search is to run two simultaneous searches—one forward from
the initial state and the other backward from the goal—hoping that the two searches meet in
the middle. The motivation is that b^(d/2) + b^(d/2) is much less than b^d. b is branch factor, d is depth. "
the initial state and the other backward from the goal—hoping that the two searches meet in
the middle. The motivation is that b^(d/2) + b^(d/2) is much less than b^d. b is branch factor, d is depth. "
----- section 3.4.6 in Artificial Intelligence - A modern approach by Stuart Russel and Peter Norvig
No comments:
Post a Comment