|
Data Structures and Algorithms
with Object-Oriented Design Patterns in C# |
Program 
defines the Copy method
of the DynamicArray class.
This method provides a way to copy the elements of one array to another.
The Copy method is intended to be used like this:
DynamicArray a = new DynamicArray(5); DynamicArray b = new DynamicArray(5); // ... b.Copy(a);The effect of doing this is to copy the elements of array a to the elements of array b. Note that after the copy, a and b still refer to distinct DynamicArray instances.
Program shows a simple implementation
of the Copy method.
To determine its running time,
we need to consider carefully the execution of this method.
Program: DynamicArray class Copy method.
First, we observe that the Copy method detects and avoids self-copies. That is, the special case
a.Copy(a);is handled properly by doing nothing.
If the array sizes differ, a new array of objects is allocated. As discussed above, this operation takes O(n) in the worst case, where n is the new array length.
Next, there is a loop which copies one-by-one the elements of the input array to the newly allocated array. Clearly this operation takes O(n) time to perform. Finally, the baseIndex field is copied in O(1) time. Altogether, the running time of the Copy method is T(n)=O(n), where n is the size of the array being copied.
Copyright © 2001 by Bruno R. Preiss, P.Eng. All rights reserved.