Beefy Boxes and Bandwidth Generously Provided by pair Networks
Come for the quick hacks, stay for the epiphanies.
 
PerlMonks  

RE: Re: finding min and max of array recursivly

by mbond (Beadle)
on Sep 28, 2000 at 17:53 UTC ( [id://34388]=note: print w/replies, xml ) Need Help??


in reply to Re: finding min and max of array recursivly
in thread finding min and max of array recursivly

Actually mine is (3n/2)+2, BUT doing this recursivly is a poor choice .. It is an assignment for class ... I have a algorithum almost identical to yours, that i use for production at work ... but that isn't a luxury right now. thanks for pointing out the 1 ... using too many different languages right now and getting cnfused :) although it still prints out the same results ... I don't think it is recursing properly to all values of the array.

Replies are listed 'Best First'.
RE: RE: Re: finding min and max of array recursivly
by japhy (Canon) on Sep 28, 2000 at 19:32 UTC
    Hmm, upon further inspection your algorithm is the following:
    sub divide { my $mid = @_/2; $ITER++; return if @_ == 1; divide(@_[0 .. $mid - 1]); divide(@_[$mid .. $#_]); } for (10 .. 30) { $ITER = 0; divide(1 .. $_); printf "%2d %2d\n", $_, $ITER; }
    The order of this is N, really. Specifically, it's 2*N-1. T(N) is the time it takes to call divide() for a list of N values:
    T(1) = 1 T(2) = 1 + 2*T(1) T(4) = 1 + 2*T(2) ... T(N) = 1 + 2*T(N/2)
    We can then expand backwards from the generality:
    T(N) = 1 + 2*T(N/2) = 1 + 2*(1 + 2*T(N/4)) = 1 + 2 + 4*T(N/4) --> = 3 + 4*T(N/4) = 3 + 4*(1 + 2*T(N/8)) = 3 + 4 + 8*T(N/8) --> = 7 + 8*T(N/8) = 7 + 8*(1 + 2*T(N/16)) = 7 + 8 + 16*T(N/16) --> = 15 + 16*T(N/16)
    The general equation here is T(N) = 2^k - 1 + 2^k * T(N / 2^k). We will make the following substitution: k = log(N) (base 2). We now have:
    T(N) = 2^k - 1 + 2^k * T(N / 2^k) = 2^(log N) - 1 + 2^(log N) * T(N / 2^log(N)) = N - 1 + N * T(N/N) = N - 1 + N * 1 = 2*N - 1


    $_="goto+F.print+chop;\n=yhpaj";F1:eval
      Unless i am mistaken somewhere (which is always possible),
      T(n) = 2*T(N/2) + 2  : not + 1.. there are 2 comparisons.
      
      the equation should simplify as follows:
      let n = 2^k;
      
      T(n) = 2^(k-1)+2^(k-1) + ... + 8 + 4 + 2
           = 2^(k-1)+21+2+4+ ... + 2^(k-2)
           = 2^(k-1)+2(2^(k-1) - 1/2-1)
           = 2^(k-1) + 2^k - 2
           = 2^(k-1)/2 + 2^k - 2
           = 3*2^k/2 - 2
           =  3n/2  -  2
      
      not that it REALLY matters inthe grander scheme of things ...
      but i think that is right ... 
      
        D'oh. Yeah. You're right. Well, we're both right. The runtime is between 2N-1 and 1.5N-2, depending on the ACTUAL number of calculations that end up needing to be done.

        $_="goto+F.print+chop;\n=yhpaj";F1:eval

Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: note [id://34388]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this?Last hourOther CB clients
Other Users?
Others perusing the Monastery: (4)
As of 2024-03-29 14:46 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found