Need help with function..

This is a discussion on Need help with function.. within the C++ Programming forums, part of the General Programming Boards category; ive never studied or heard of the proof for that. not that i dont believe there is one, ive just ...

  1. #16
    Registered User
    Join Date
    Oct 2006
    Location
    Canada
    Posts
    1,243
    ive never studied or heard of the proof for that. not that i dont believe there is one, ive just never heard mention of it before. do you have a link to one? preferably not in form of a thesis.

  2. #17
    Banned master5001's Avatar
    Join Date
    Aug 2001
    Location
    Visalia, CA, USA
    Posts
    3,685
    Just think of it with pure logic. Take a pile of puzzle pieces (preferably a small one since this is a simple concept). Don't try to put it together, but instead just consider what the maximum speed you could possibly put it together.

    You will need to do the following:
    1) Have something to put together.
    2) Identify the existance of each individual piece.
    3) Arrange the individual piece into the larger collection.
    4) Go to the next piece until the operation is complete.

    Now, if you tell a computer to do the same, it will follow similar logic, right? Unless there is some sort of predefined pattern to the puzzle pieces (or a bunch of them fell out of the box already put together) then you have no way of short cutting this system. What makes you assume your program can do otherwise?

  3. #18
    Frequently Quite Prolix dwks's Avatar
    Join Date
    Apr 2005
    Location
    Canada
    Posts
    8,046
    I always liked this explanation (it was for sorting algorithms, but it works here too):

    Say you have compared all of the numbers in a set except for one with each other and found their minimum. How can you know whether this number is in fact the minimum without checking if it is less than the last number?

    So in other words, you can't get any better than n-1 comparisons, which is O(n). (You have to look at every number in order to find the lowest in the bunch.)

    . . . or something like that. Knuth said it better.
    dwk

    Seek and ye shall find. quaere et invenies.

    "Simplicity does not precede complexity, but follows it." -- Alan Perlis
    "Testing can only prove the presence of bugs, not their absence." -- Edsger Dijkstra
    "The only real mistake is the one from which we learn nothing." -- John Powell


    Other boards: DaniWeb, TPS
    Unofficial Wiki FAQ: cpwiki.sf.net

    My website: http://dwks.theprogrammingsite.com/
    Projects: codeform, xuni, atlantis, nort, etc.

  4. #19
    Registered User
    Join Date
    Oct 2006
    Location
    Canada
    Posts
    1,243
    i never said anything about a program, let alone a program i made.

    i dont understand how your analogy is to explain the proof. a funny thing about logic (in the sense your talking about) is that it is ambiguous and discussions can be made about the smallest topic that go on forever. i have read pseudocode and proofs that prove an algorithms complexity using only mathematics (and basic english terms, not 'logic' though). i am interested in seeing the (mathematical) proof that you mentioned. also if a sorting algorithm (which i think the best today are O(n*log(n)) are possible to be improved significantly, ie better than O(n), then you could use that algorithm and take the first element of that list (which would be O(1)) and have that the same complexity for a min algorithm as the sorting algorithm.

  5. #20
    Frequently Quite Prolix dwks's Avatar
    Join Date
    Apr 2005
    Location
    Canada
    Posts
    8,046
    Why not read my post? It's not exactly a proof, but I'm sure you can find something like that if you google around. Or, if you have Knuth's book on sorting algorithms, you can look it up in there. It's near the beginning. Right where he describes the classes of sorting algorithms, and asks that you inform him immediately if you discover a new super-sort.
    dwk

    Seek and ye shall find. quaere et invenies.

    "Simplicity does not precede complexity, but follows it." -- Alan Perlis
    "Testing can only prove the presence of bugs, not their absence." -- Edsger Dijkstra
    "The only real mistake is the one from which we learn nothing." -- John Powell


    Other boards: DaniWeb, TPS
    Unofficial Wiki FAQ: cpwiki.sf.net

    My website: http://dwks.theprogrammingsite.com/
    Projects: codeform, xuni, atlantis, nort, etc.

  6. #21
    Banned master5001's Avatar
    Join Date
    Aug 2001
    Location
    Visalia, CA, USA
    Posts
    3,685
    In what way was what me and nadroj too convoluted for you to understand? Since you must identify ALL components of whatever you are sorting, you can at best only be as fast as looking at each item once. If you do not look at all elements of whatever it is that you are sorting, you potentially leave something unsorted. So your best case sort in sorting is to more or less proof read something that is already sorted and just look at each piece and acknowledge that it is sorted (i.e. a function that doesn't even really do anything other than read pre-sorted data).

    What is debateable is what can most rapidly confirm that the data is already sorted. You have the web at your access to my friend. I am not going to search stuff you are capable of looking up on your own. You were given satisfactory explanation to the logic. Even if you have multiple CPU's each reading part of a pile of data, there is always going to be a point where things are only processed on an individual basis. No matter what. I applaud that you are so boldy trying to make something "better."

  7. #22
    Registered User
    Join Date
    Oct 2006
    Location
    Canada
    Posts
    1,243
    dwks, my reply was to master5001, i never said anything about you. also, after i posted your post didnt show up until after i refreshed.

    i realize that this sort of thing is logical and only makes sense that you would have to look at each number (otherwise you could be missing the actual min, etc).

    the super-sort, is that the paragraph before or after the "typo $1 cheque" thing? (or was that Dijkstra). anyways, Knuth's collection scares me!

  8. #23
    Banned master5001's Avatar
    Join Date
    Aug 2001
    Location
    Visalia, CA, USA
    Posts
    3,685
    Given your reply, and your understanding of the process and dwks' alternative explanation then I think we are good.

  9. #24
    Registered User
    Join Date
    Oct 2006
    Location
    Canada
    Posts
    1,243
    ya, in what way was what me and master said too convoluted for you?

    well you are correct in that i do have the web to access. i only figured that since you mentioned the mathematical proof in your post that i was interested in seeing it. im not asking you to go find it for me, and im not going to look anyways, but it just made it seem that you had it available.

  10. #25
    Frequently Quite Prolix dwks's Avatar
    Join Date
    Apr 2005
    Location
    Canada
    Posts
    8,046
    dwks, my reply was to master5001, i never said anything about you. also, after i posted your post didnt show up until after i refreshed.
    I know, I could tell by the time you posted and the length of your post. That's why I suggested you read it. Sorry if I came across as implying you had ignored my post and skipped over it. [edit] That's what just happened to this post, too. [/edit]

    the super-sort, is that the paragraph before or after the "typo $1 cheque" thing? (or was that Dijkstra). anyways, Knuth's collection scares me!
    I don't remember. I think Knuth has something like that: you know, offering $1 in whatever year for the first error discovered in his book, $2 the second year, $4 the third, etc. You could probably make a small fortune by now if you managed to actually find an error in one. :P
    dwk

    Seek and ye shall find. quaere et invenies.

    "Simplicity does not precede complexity, but follows it." -- Alan Perlis
    "Testing can only prove the presence of bugs, not their absence." -- Edsger Dijkstra
    "The only real mistake is the one from which we learn nothing." -- John Powell


    Other boards: DaniWeb, TPS
    Unofficial Wiki FAQ: cpwiki.sf.net

    My website: http://dwks.theprogrammingsite.com/
    Projects: codeform, xuni, atlantis, nort, etc.

  11. #26
    Registered User
    Join Date
    Oct 2006
    Location
    Canada
    Posts
    1,243
    hes going in powers of 2? wow.. i thought it was constant $1 USD.

    but thats ok.. it did seem like you were being smart and saying "well why not read MYpost then, smrtas?"

  12. #27
    Frequently Quite Prolix dwks's Avatar
    Join Date
    Apr 2005
    Location
    Canada
    Posts
    8,046
    Yeah, I'm pretty sure it's powers of two.
    [edit] I guess it's powers of two, but actually cents, not dollars.
    You are entitled to a reward of at least $2.56 if you are the first person to report a bona-fide error not on those lists. Each page tells you how to report an error for the book in question.
    http://www-cs-faculty.stanford.edu/~knuth/books.html [/edit]

    I guess I didn't put enough smilies in.
    dwk

    Seek and ye shall find. quaere et invenies.

    "Simplicity does not precede complexity, but follows it." -- Alan Perlis
    "Testing can only prove the presence of bugs, not their absence." -- Edsger Dijkstra
    "The only real mistake is the one from which we learn nothing." -- John Powell


    Other boards: DaniWeb, TPS
    Unofficial Wiki FAQ: cpwiki.sf.net

    My website: http://dwks.theprogrammingsite.com/
    Projects: codeform, xuni, atlantis, nort, etc.

  13. #28
    Registered User
    Join Date
    Oct 2006
    Location
    Canada
    Posts
    1,243
    lol, cheers

  14. #29
    Frequently Quite Prolix dwks's Avatar
    Join Date
    Apr 2005
    Location
    Canada
    Posts
    8,046
    End note: actually, it's $2.56 for one error, $5.12 for the next, and so on. Not by year, by error number.
    http://www.upto11.net/generic_wiki.p...h_reward_check
    http://www.nationmaster.com/encyclop...h-reward-check
    dwk

    Seek and ye shall find. quaere et invenies.

    "Simplicity does not precede complexity, but follows it." -- Alan Perlis
    "Testing can only prove the presence of bugs, not their absence." -- Edsger Dijkstra
    "The only real mistake is the one from which we learn nothing." -- John Powell


    Other boards: DaniWeb, TPS
    Unofficial Wiki FAQ: cpwiki.sf.net

    My website: http://dwks.theprogrammingsite.com/
    Projects: codeform, xuni, atlantis, nort, etc.

  15. #30
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Quote Originally Posted by nadroj View Post
    you mean there isnt one yet!
    For a list that contains unordered numbers, there is no other way than to compare every single item. Obviously, if you have a sorted list, you can find things in it much quicker. Unfortunately, it take more than O(n) to sort the list, so there's no gain in that for a single find. (And you can do "max and min" in O(n) as well - because you just check for both largest and smallest on every item, and that is also O(n)).

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

Page 2 of 3 FirstFirst 123 LastLast
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Compiling sample DarkGDK Program
    By Phyxashun in forum Game Programming
    Replies: 6
    Last Post: 01-27-2009, 02:07 AM
  2. Seg Fault in Compare Function
    By tytelizgal in forum C Programming
    Replies: 1
    Last Post: 10-25-2008, 03:06 PM
  3. Another syntax error
    By caldeira in forum C Programming
    Replies: 31
    Last Post: 09-05-2008, 01:01 AM
  4. Replies: 28
    Last Post: 07-16-2006, 11:35 PM
  5. const at the end of a sub routine?
    By Kleid-0 in forum C++ Programming
    Replies: 14
    Last Post: 10-23-2005, 06:44 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21