Re: Calculating distances in O(1)
- From: cri@xxxxxxxx (Richard Harter)
- Date: Sat, 14 Jan 2006 16:06:32 GMT
On Sat, 14 Jan 2006 00:16:23 -0500, "Chuck F. " <cbfalconer@xxxxxxxxx>
wrote:
>racygirl wrote:
>>
>> I was just wondering, is it possible to write a solution to the
>> following problem with the following criteria:
>>
>> 1. it must be as efficient as possible at run-time
>> 2. be in O(1)
>> 3. and be memory efficient
>>
>> The problem is:
>> Find the total distance between any two cities if:
>> Given
>> source city destination city distance
>> 0 1 5 mi.
>> 1 2 2 mi.
>> 2 3 7 mi.
>> 3 4 8 mi.
>>
>> etc... for N cities.
>> Example: distance(0, 4) = 5+2+7+8 = 22 The distance function is
>> being called millions and millions of times and the list of
>> cities and distances do not change after the program starts.
Create an array of distances from city 0. The distance from city A to
city B is the difference of their distances from city 0. For your
data the array looks like:
city 0 1 2 3 4
distance 0 5 7 14 22
Example: the distance from city 2 to city 4 is 22-7=15.
Something you might want to think about if this is homework (I imagine
it is) is how O(1) solutions have to work, vs how O(log n) solutions
work. For example, a binary tree is almost certainly the wrong
answer. Why is that?
Richard Harter, cri@xxxxxxxx
http://home.tiac.net/~cri, http://www.varinoma.com
The eternal revolution has its needs - its slogans to be chanted,
its demonstrations to be held, its children to eat.
.
- Prev by Date: Object Orientated boucing ball
- Next by Date: Re: C Programmer Needed
- Previous by thread: Re: Calculating distances in O(1)
- Next by thread: Re: Calculating distances in O(1)
- Index(es):
Relevant Pages
|
