Author: Robert Hyatt
Date: 18:50:35 05/15/01
Go up one level in this thread
On May 15, 2001 at 18:04:28, Jesper Antonsson wrote: >On May 15, 2001 at 13:02:11, Robert Hyatt wrote: > >>On May 15, 2001 at 11:54:10, David Rasmussen wrote: >> >>>On May 15, 2001 at 06:35:42, Martin Schubert wrote: >>> >>>> >>>>O(...) is about asymptotical behaviour. If n is bounded, it doesn't make sense >>>>to talk about asymptotical behaviour. >>>> >>>>Martin >>> >>>Exactly. >> >> >>not exactly. O(n) discussions can be asymptotical in nature, if the "bound" >>is large enough to be considered infinite. >> >>IE I am _still_ waiting for someone to post a problem description (real-word >>problem) that is unbounded in any way. To date, no one has. Which means all >>real-world problems are O(1) and that definition is _still_ worthless and >>pointless. > >Nonsense. This is a theory discussion and I don't give a rats ass about >"real-world" problems. In chess, when you go above a certain depth, the time >taken for the algorithm to complete doesn't increase. In the travelling salesman >problem, for example, another city always increase the time taken for the >algorithm to complete. That's why chess is O(1) and the TSP is not. As I said, real-world. The TSP problem is a real-world problem that is not unbounded in size, simply because the number of cities in the world is finite and countable. Chess may or may not be finite. The 50-move rule has not been a part of the game forever. It is relatively recent. And within the past 20 years it has been suspended for specific endings, and then later the suspension was lifted. If we go back to prior-50-move-rule, the game is most certainly infinite in any way you care to define infinite, for the real-world. There is no way to search a tree to depth 1,000,000 for example. Not now. Not ever. Never. Even if we know the game can be solved in that depth of search. Yet the tree _still_ exhibits O(W^(D/2)) complexity for all D that I can reach now, or that I will _ever_ be able to reach. To call this O(1) is nonsense. Perhaps that is why theorists are somewhat useless? You are telling me that as I increase D, the search time remains O(1), yet every time I do it, it takes over 6X longer for the next search. One of those is wrong. I can prove which with a simple program that I already have... O() does _perfectly_ at predicting the run-time of alpha/beta. For today. For next Century. For time at the end of the universe. Each successive D will multiply by roughly a factor of 6 the time for the previous D. And if D happens to be limited, in some artificial way, but in a way that will never affect the actual search, the so what? Big-Oh _still_ predicts the run-time correctly in my model, not in the O(1) model... Therefore the O(1) model is not only useless... it is worthless... > >>Big-Oh is _still_ a conceptual way to predict program run-time as the input >>is increased in some way. I posted a direct quote from one theory book >>yesterday. I can post others that make the same statement... > >You also quoted a definition. Use it. I am. It predicts the run-time of an algorithm. I've not varied from that definition one iota. O(1) doesn't predict _anything_... > >>In "theory" this "asymptotic behavior" might make sense. In practical terms, >>it does not, and all the complexity analysis of algorithms, for any real-world >>algorithm you name, must be of O(1) which is nonsense to those of us that are >>working on algorithms. > >Yes, I agree, that's nonsense.
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.