CMPT 115 Lecture Notes - Lecture 17: Perfect Hash Function, Pseudorandom Number Generator, Hash Table
Document Summary
Notes written by michael horsch, mark eramian, ian mcquillan, lingling jin, and dmytro dyachuk. 1 introduction: we"ve seen di erent ways to search arrays: Binary search ((log n): binary search was more e cient, but required the table to be sorted, we can do betterwithout requiring a sorted array, a table is just a list of records with di erent elds: 1: like an array, each table row has an index starting at 0, a table can easily be represented by an array of structures. Team reftostring teamname int wins int losses end team. Team westernconference[8: a simple array of, say, integers is just a table with a single column, if the table is an array: Linear search o(n) worst case time complexity. Binary search (if the table is sorted already) o(log n) worst case time complexity: if the table is a linked-list: Linear search o(n) worst case time complexity: if the table is a binary search tree:
