Prev: Simulink and ModelSim automation
Next: Skewed GED Random Number Generator
From: Walter Roberson on 9 Mar 2010 18:30
Ruben wrote:

> I don't exactly understand what you mean with 'is of order N*log(N)', could you explain it? Would be great.

It has to do with the computational complexity of the code; that is, it has to
do with how much longer it takes for the code to work on a larger problem.

Code that takes a constant amount of time is said to have O(0) (that's capital
Oh with zero in brackets) complexity -- just like the differential of a
constant function in calculus, the time doesn't change as you give it a bigger
problem (which probably means it ignores the input.)

Code that examines each input value once, or any fixed number of times that is
independent of the size of the problem, is said to have O(N) ("order N")
complexity; N is used to mean "the size of the input"; the length of time it
takes to compute a larger problem is linear in the size of the problem.

The best sort algorithms take O(N*log(N)) ("order N log N") time; that is, the
time to compute a larger problem increases faster than just the increase in
the size of the problem itself, but the rate of increase slows down as the
problem gets bigger -- so a problem with 1000 inputs would take about 3000
times longer than a single input, and a problem with 10000 inputs would take
about 40000 times longer than a single input. You'd rather have an O(N)
algorithm, but O(N*log(N)) is not so bad.

A naive sort algorithm takes time N*(N-1)/2 which is N^2/2 - N/2. In
calculating algorithm complexity, you only list the term that grows the
fastest as the size of the problem grows, so you would ignore the -N/2 part,
leaving just N^2/2 for the moment. You also ignore the linear factors, so the
naive sort algorithms are said to take time O(N^2) ("order N-squared") -- so a
problem with 1000 inputs would take a million times longer than a single
input, and a problem with 10000 inputs would take 100 million times longer
than a single input. This is bad news: you want to avoid such algorithms
(though they sometimes have their place if you sure you are only working on
very small problems.)

An algorithm that tried to select distinct random numbers by selecting one,
determining whether it was already selected or not and either way "throwing it
back in the pot" (selection with replacement) is not guaranteed to _ever_
finish. If you discuss the "worst case" complexity of the algorithm, it would
be said to be O(infinity). If, though, you want to discuss the _average_ (or
"expected") time for such an algorithm, I would have to work through the math
of it, but I believe that it is at least O(exp(x)), which grows faster than
any polynomial. This is very bad news for computational purposes, and often
means that it is not feasible to handle a problem with more than 15 to 20 inputs.
From: Ruben on 10 Mar 2010 06:30
Hi Walter,

Thanks for your extended reply. It is completely clear for me now what you meant with N*log(N). I understand that randperm uses the best algorithm: it is finite and does not take big amounts of time. Therfore I will use the by you recommended 'randperm' method. Thanks for help!

Ruben
From: Greg Heath on 10 Mar 2010 23:53
On Mar 9, 3:58 pm, Walter Roberson <rober...(a)hushmail.com> wrote:
> Ruben wrote:
> > The 12 numbers have to be different integers chosen from 1:12 (so each number from 1 to 12 is used once).What is the best method in matlab to generate these 12 numbers in a random way? Thanks for help!
>
> randperm(12)
>
> is of order N*log(N) and a guarantee of a finite run time.
>
> Any routine that uses selection "with replacement" and compares against the
> answers already selected has an infinite tail on the run time.

Does that mean there is no finite order bound if, on the ith trial
you select x(i) from x = randperm(N) until all integers 1:N
were chosen?

Hope this helps.

Greg
From: Greg Heath on 11 Mar 2010 01:29
On Mar 10, 11:53 pm, Greg Heath <he...(a)alumni.brown.edu> wrote:
> On Mar 9, 3:58 pm, Walter Roberson <rober...(a)hushmail.com> wrote:
>
> > Ruben wrote:
> > > The 12 numbers have to be different integers chosen from 1:12 (so each number from 1 to 12 is used once).What is the best method in matlab to generate these 12 numbers in a random way? Thanks for help!
>
> > randperm(12)
>
> > is of order N*log(N) and a guarantee of a finite run time.
>
> > Any routine that uses selection "with replacement" and compares against the
> > answers already selected has an infinite tail on the run time.
>
> Does that mean there is no finite order bound if, on the ith trial
> you select x(i) from x = randperm(N) until all integers 1:N
> were chosen?

Forget that.

n = 0;
h = zeros(1,N) % histogram
while min(h) == 0
n = n+1;
m = 1+round((N-1)*rand);
y(n) = m; % random stream
h(m) = h(m)+1;
end

is obviously faster.

Hope this helps.

Greg

From: Walter Roberson on 11 Mar 2010 01:51
Greg Heath wrote:
> On Mar 9, 3:58 pm, Walter Roberson <rober...(a)hushmail.com> wrote:

>> randperm(12)
>>
>> is of order N*log(N) and a guarantee of a finite run time.
>>
>> Any routine that uses selection "with replacement" and compares against the
>> answers already selected has an infinite tail on the run time.

> Does that mean there is no finite order bound if, on the ith trial
> you select x(i) from x = randperm(N) until all integers 1:N
> were chosen?

Selecting x(i) on the ith trial is not selection "with replacement", it
is selection "without replacement".

In selection "with replacement", the value (or object) just picked is
put back into the pool, available to be picked again with the same
probability it had before. In selection "without replacement", the value
(or object) just picked is removed from the pool that is selected from,
changing the odds of selecting any particular one of the other members
(unless, of course, the pool is infinite!).

If x(i) is selected on the i'th trial, then x(i-1) is not available for
selection on the i'th trial, so you are in a "without replacement"
situation.
First  |  Prev  |  Next  |  Last
Pages: 1 2 3
Prev: Simulink and ModelSim automation
Next: Skewed GED Random Number Generator