Address Calculation FunctionsSuppose we have an array A with n distinct elements in some order. Suppose further that we have some function f that is one-to-one onto A. For example, f might be a rotation, or a sort, or a reversal. If our objective is to be able to determine the i’th element of f(A) we can go either of two ways. We can apply f to A and extract the i’th element of the transformed array, e.g. A' = f(A) val = A'[i]The other choice is to do an address calculation. We determine a function f’ such that A'[i] = A[f'(i)]. In other words for each element in A’ f’ specifies the location in A where the element came from. (f and f’ are distinct because f is a a mapping from array to array and f’ is a mapping from int to int.) What f’ does is effect a permutation of the elements of A. One way to effect f’ is to record the permutation in an array, also of length n. The space required is O(n) and the access time is O(1). At this point it is worthwhile making a point about functions. In set theory a function is a set of ordered pairs with one member of the pair coming from the domain and the other from the range; that is, functions are uniquely defined by their mappings. In recursive function theory, otoh, functions are defined by their recursion equations; that is, functions are defined by algorithms. What I am getting at here is that there will be an finite (n! in fact) number of mappings (permutations) and an infinite number of corresponding address calculation functions. The permutations divide the address calculation functions into equivalence classes. The different functions in a given class do the same thing but have different space and time costs. This conception makes for some interesting questions. One of the things we would like to know is: Given a function f onto A what are the functions f’ that have minimum costs. Thus we know that for any f there is always an f’ that is O(n) in space and O(1) in time. Rotation and reveral are functions for which f’ is O(1) in space and time. More generally, for any f can we find an f’ that O(1) in both space and time? O(log n) for one and O(1) for the other? O(log n) for each? Another thing that we can ask is: Consider the class of address calculation functions that are O(1) in space and time. How big is their equivalence class. Does it comprise the entirety of the permutations or is it some subset of the permutations? Is there any interesting characterization of that subset? If you accept, answering these questions will be your task for the weekend. There will be no grade but there will be applause. This page was last updated July 1, 2004. |