Author: Dann Corbit
Date: 08:27:46 05/09/01
Go up one level in this thread
On May 09, 2001 at 10:12:30, Ricardo Gibert wrote:
>On May 09, 2001 at 02:00:25, Dann Corbit wrote:
>
>>For those of you who don't want to perform your own web search, just choose one
>>of these:
>>
>>http://hissa.nist.gov/dads/HTML/bigOnotation.html
>>http://bio5495.wustl.edu/textbook-html/node15.html
>>http://umastr.math.umass.edu/~holden/Math136-99_projects/Amstutz-OBoyle-Petravage/big-o.html
>>http://www.eecs.harvard.edu/~ellard/Q-97/HTML/root/node8.html
>>http://classes.monterey.edu/CST/CST338-01/world/BigO.html
>>http://shalim.csustan.edu/~john/Classes/CS3100_DataStructures/Previous_Semesters/1999_04_Fall/Examples/big-O
>>
>>CS:201, FCOL!
>
>Big-O notation is used to describe asymtotic behavior. It commonly used to
>describe the "running time" of an algorithm. If an algorithm is O(f(n)), n is
>understood to be a finite, but *unbounded*. (For some reason, "unbounded" gets
>confused with infinity. This is an error, but let's not get into that. It isn't
>relevant here)
>
>In chess, n in is bounded. This is a critical distinction, that means chess is
>*not* NP.
GREAT! Then it's computable. What's the answer, win-loss-draw?
;-)
>If we were to allow the size of the chessboard to expand, then the
>number of steps in its solution would be NP (extremely likely, but not certain!)
{Not you too!}
WHAT UTTER POPPYCOCK. Please provide a citation from a reputable source that
says if we have a bound on the data our algorithm becomes O(1). That's so
nonesensical that it renders an analysis of algorithsm as completely pointless.
ALL INPUTS ARE BOUNDED!!!!!
There is no such requirement anywhere in the literature. The running time of
the algorithm can be discerned by examination of the algorithm alone. In fact,
that is how it is always done.
Using this absurd reasoning, I will now demonstrate that BOGOSORT is O(1).
Here is an implementation of bogosort. Bogosort sorts by replacing the current
vector with a random permutation. After each permutation it scans the list to
see if the data is ordered.
/* A BogoSort(tm) implementation bsort(), like qsort()
Public domain by Tom Torfs
Define TEST for a demonstration */
#include <stdlib.h>
#include <time.h>
/* This BogoSort(tm) routine performs very
well for an already sorted set of data */
void bsort(void *base,
size_t nmemb,
size_t size,
int (*compar)(const void *, const void *))
{
static int seeded = 0;
size_t elem1, elem2;
size_t count;
unsigned char temp;
unsigned char *cbase = base;
int sorted;
/* seed PRNG if first call */
if (!seeded)
{
srand((unsigned)time(NULL));
seeded = 1;
}
/* less than 2 elements are always sorted */
if (nmemb < 2)
return;
for (;;)
{
/* check if sorted */
sorted = 1;
for (elem1=0; elem1<nmemb-1; elem1++)
{
if (compar((const void *)(cbase+elem1*size),
(const void *)(cbase+(elem1+1)*size)) > 0)
{
sorted = 0;
break;
}
}
if (sorted)
return;
/* not sorted yet, generate a random permutation */
for (elem1=0; elem1<nmemb; elem1++)
{
elem2 = rand() / (RAND_MAX / nmemb + 1);
/* swap elem1 and elem2 bytewise */
for (count=0; count<size; count++)
{
temp = cbase[elem1*size + count];
cbase[elem1*size + count] = cbase[elem2*size + count];
cbase[elem2*size + count] = temp;
}
}
}
}
#ifdef TEST
#include <stdio.h>
int intcmp(const void *a, const void *b)
{
int x = *(const int *)a;
int y = *(const int *)b;
return (x > y) - (x < y);
}
int main(void)
{
char buf[10];
int *array;
int n, count;
puts("BogoSort(tm) demonstration\n");
do
{
printf("How many elements to sort ? ");
fflush(stdout);
}
while (fgets(buf, sizeof buf, stdin)==NULL
|| sscanf(buf, "%d", &n)!=1
|| n<0);
array = malloc(sizeof *array * n);
if (array==NULL)
{
printf("Out of memory.");
return EXIT_FAILURE;
}
puts("Enter data to be sorted:");
for (count=0; count<n; count++)
{
do
{
printf("Enter value for element number %5d: ", count);
fflush(stdout);
}
while (fgets(buf, sizeof buf, stdin)==NULL
|| sscanf(buf, "%d", &array[count])!=1);
}
printf("Sorting...\n");
bsort(array, n, sizeof *array, intcmp);
printf("Results:\n");
for (count=0; count<n; count++)
printf("Element number %5d: %5d\n", count, array[count]);
return EXIT_SUCCESS;
}
#endif
Now, as you will notice above, the input of vector length is a size_t.
Supposing that this is an unsigned 64 bit integer (which is the largest
precision arithmetic type guaranteed in the ANSI C language), that will give a
maximum possible vector length of 2^64 - 1 = 18446744073709551615. Now, if we
take a random vector and randomly choose a candidate for the first element, we
have it right or wrong. Assuming worst case (the elements are all distinct) we
have 1/18446744073709551615 odds of getting it right. Now, to get the second
element right, there are only 18446744073709551615-1 elements left, so we have a
1/18446744073709551614 chance of picking it at random. Similarly for each of
the succeeding elements.
Obviously, since the probabilities must multiply (each succeeding event is
dependent on the previous) the probability is:
1/(18446744073709551615!) {exclamation point for factorial} that our data set
will be ordered.
But WAIT! That's just a constant. A rather large constant, but a constant
none-the-less. Hence our running time is O(1).
Q.E.D.
FOR CRYING OUT LOUD!
And happy sorting.
[snip]
This page took 0.01 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.