Author: Robert Hyatt
Date: 19:36:56 05/09/01
Go up one level in this thread
On May 09, 2001 at 16:10:09, Andrew Dados wrote: >On May 09, 2001 at 16:05:37, Robert Hyatt wrote: > >>On May 09, 2001 at 16:02:59, Andrew Dados wrote: >> >>>On May 09, 2001 at 15:49:26, Dann Corbit wrote: >>> >>>>Suppose that I have a collection of sorting algorithms. >>>> >>>>I know that the count of vector elements to be put into sorted order will never >>>>exceed a size_t. >>>> >>>>I have a counting sort that can sort in O(n*log(element_length)) >>>> >>>>I have a relaxed-quick-heapsort that can sort in O(log(n!)) >>>> >>>>I have an shell sort that can sort in O(n^(1 + epsilon/n)) >>>> >>>>Now, since we know that the count will never exceed a size_t, have all these >>>>calculations really simplified to O(1)? Is there really no way to choose >>>>between them? If they really do retain their original behaviors, then what is >>>>the utility of declaring them to be O(1)? >>> >>>In chess, no matter what position, it is guaranteed to be solved after less then >>>2^100 steps. Now find me such a sorting algorithm that will require less then >>>Constant steps * no matter what size_t *. Can't you see that simple difference? >>> >>>-Andrew- >>>-Andrew- >> >> >>Where does that 2^100 steps come from? > >If you run mini-max you can visit only legal positions in order to solve >starting position. I just estimate that at 2^100 (or whatever constant >approximates it better). > >>And from complexity theory what does it matter anyway? > >Guaranteed fixed number of steps means O(1) afik. OK,... we now know the following: sorting names of people is O(1) as there is a finite number of people. Weather forecasting is O(1) as there are a finite number of samples since we can't measure atmospheric conditions (used by the models) at a subatomic level. CFD is O(1) since the same condition holds true for fluid pressure since it can't be measured at the subatomic level. Nuclear Fission and Fusion models are O(1) since there are a finite number of atoms in the universe that can take part in the reactions. I'm having a hard time coming up with _any_ non-O(1) problem, in fact. Unless this definition of O(1) is flawed.
This page took 0 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.