Author: Dann Corbit
Date: 12:28:27 05/09/01
Go up one level in this thread
On May 09, 2001 at 15:18:12, Andrew Dados wrote: >On May 09, 2001 at 15:11:41, Eugene Nalimov wrote: > >>Ok, here is simple example: let's consider sorting but limit the input by (a) >>limiting # of digits in each number (e.g. 1024 bits), and (b) limiting # of >>elements in the sequence we want to sort (e.g. max 10**40 elements). Yes, >>theoretical # of operations that are necessary to sort such a sequence is >>limited. But, nevertheless, you still can say that >>* insertion sort is O(N*N), >>* quick sort is O(N*ln(N)) on average, but O(N*N) in the worst case, >>* heap sort is O(N*ln(N)) in the worst case. >>So I don't see why the fact that something is finite changes something in the >>complexity tree search. >> >>Eugene > >Wrong example. Instead consider sorting a set (2,42,15,103,37). Sort it; save a >solution. If we save the solution, then we have traded computational cost for storage cost. >Then what is a cost of sorting exact same set again? We are using a different algorithm. It won't help in chess anyway, since we can't compute it and if we could compute it we could not save it. Of course Eugene knows this better than anyone on earth probably. If we do compute it then it is exactly the same as the first time, probably O(n*log(n)) if we use comparisons. If we use a clever integer sorting method, it has been demonstrated that it can be reduced to O(n*log(log(n))) by Stefan Nilsson: http://www.nada.kth.se/~snilsson/public/papers/sorting/ If we preview the problem we can put them in order in the first place and then it really is O(1) for that set, but we have not done this with chess. Solving a given problem set has no connection to the efficiency of the algorithm[1]. >There is infinite sets of numbers to sort; there is only one chess position to >solve.... There is only one starting position to solve but that position is what is known as "intractible" or "incomputable" because chess is.... exponential. [1] Except that degenerate cases may not show big-O behavior. And except that you can estimate a physical bound for a given instance of data. That's the whole purpose of analysis of algorithms. If chess is O(1), then TSP is O(1).
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.