Author: Jeremiah Penery
Date: 17:42:29 05/13/01
Go up one level in this thread
On May 13, 2001 at 19:17:36, Jesper Antonsson wrote: >On May 11, 2001 at 21:42:53, Jeremiah Penery wrote: > >>On May 11, 2001 at 16:43:38, Jesper Antonsson wrote: >> >>>My understanding of this topic is without a doubt as good or better than yours, >>>thank you very much. I agree that it is not meaningful to talk about complexity >>>for sorting 1000 items, while I don't agree that's comparable to chess. You, >>>however, doesn't seem to understand that *depth* was the input considered in the >>>start of this argument, and that *chess* is the topic. >> >>It seems you don't understand the point of the O-notation. It's not supposed to >>tell you that algorithm FOO takes time X to run on input BAR. It's supposed to >>let you _estimate_ the running time of algorithm FOO on input BAR+1 (BAR+2, >>BAR+3, etc...) when you know the running time on input BAR. ***You know that >>the algorithm will eventually complete, no matter what the input!*** But, for >>example, naming a sorting algorithm O(1) says that it will sort 1000000 numbers >>just as fast as it sorts 5 numbers. When you call a tree-searching algorithm >>O(1), when depth is the input, you're saying that it takes the same amount of >>time to search depth 500 as it does to search depth 3. Obviously, this is wrong >>for any chess program. > >This is all wrong, my friend. The "O-notation" doesn't have a "point" (or at >least not that one) Then why take the time to find the O(f(n)) of any algorithm? The point of doing it is so that you can see whether algorithm A will run faster than algorithm B (quicksort runs faster than bogosort, for example) with arbitrary input. If you have two sorting algorithms, one with O(n + 5000) and one with O(n!), you can say that for very small N, the O(n!) program will be faster, but otherwise it will be much slower. This is "point" of O(f(n)). If you don't correctly find O(f(n)) of an algorithm (or algorithms), how will you ever know which one to choose for a particular job? >and O(1) does not guarantee same running time for different >inputs. The O-notation is clearly defined, and my use adheres to the definition. O(1) is _constant_ running time, regardless of input length. You can make a graph and see this very clearly. Any algorithm with different running times for different N must use an O(f(n)) that actually has an "n" in it - O(n), O(log(n)), O(n*log(n)), O(n!), O(exp(n)), etc. >It's quite simple math, look it up. I agree, the math is quite simple.
This page took 0.08 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.