Feeds:
Posts
Comments

Archive for the ‘algorithm’ Category

Comparison of DataStructures

  • Unsorted Array:
    • Add: add the records as the last entry  fast O(1)
    • Delete a target: slow finding the target, fast at filling the hole O(n)
    • Search: sequential search slow O(n)
  • Sorted Array:
    • Add: insert the record in proper position. much record movement slow O(n)
    • Delete a target: how to handle the hole after deletion, much record movement slow O(n)
    • Search: binary search fast O(log n)
  • Linked list:
    • Add: fast if one can insert node anywhere O(1)
    • Delete: fast at disposing the node, but slow at finding the target O(n)
    • Search: sequential search slow O(n)
  • Hash table:
    • Add: fast O(1)
    • Delete: fast O(1)
    • Search: fast O(1)
  • Hash Function:
    • Maps a key to an index within a range:
      • If key type is int, key % Tsize
      • If key type is string, convert the string to an integer and then %Tsize
    • Goal of hash function:
      • fast to compute
      • even distribution
Advertisements

Read Full Post »