Thread: Memoization

  1. #1
    Banned
    Join Date
    Apr 2015
    Posts
    596

    Memoization

    Hi guys, I know what's Memoization and how it's used in dynamic programming , but there's still something not understandable for me.

    Memoization is primarily used for dynamic programming, for example in Fibonacci sequence we are calling much calls twice, so if we do an array with size n which can save every call that we called before and not to call it again, then we are declining the time complexity !

    I understand that, but who said that the time of the calling function is greater than making an array and saving to it the calls? I mean:
    without memoization, if I call F(1) once in left tree of recursive, then I will call it again in right tree, so we are calling twice F(1)
    with memoization, if I call F(1) once in left tree of recursive, then I will no't call it again in right tree, I just save F(1) and use it again , in other words we are not "calling again F(1)" .

    so I claim who said that not "calling again F(1)" will ofcourse reduce the time complexity? in other words why time complexity of using array that saves F(1) call will be smaller than calling F(1) itself?!

    thanks alot

  2. #2
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    27,078
    Did you do any research as to both the practical time cost of allocating an array and its possible time complexity? Did you write test programs to see which is faster as N becomes large?

    You went ahead and just asked before doing your homework, didn't you? I know because I decided to search the Web for "time complexity of array allocation" and lo, there were essays written by other people that should have gone some way towards answering your question.
    Last edited by laserlight; 05-21-2019 at 05:19 AM.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  3. #3
    Banned
    Join Date
    Apr 2015
    Posts
    596
    Quote Originally Posted by laserlight View Post
    Did you do any research as to both the practical time cost of allocating an array and its possible time complexity? Did you write test programs to see which is faster as N becomes large?

    You went ahead and just asked before doing your homework, didn't you? I know because I decided to search the Web for "time complexity of array allocation" and lo, there were essays written by other people that should have gone some way towards answering your question.
    thanks ! I will try by myself once again, it's not homework ! I was reading the subject of dynamic programming and faced the subject of "memoization" , if you look back to my question, isn't about specific question it's general about "memoization" !

  4. #4
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    27,078
    I mean "homework" as in "literature review and other research done prior to asking a question", not "academic assignment".
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  5. #5
    TEIAM - problem solved
    Join Date
    Apr 2012
    Location
    Melbourne Australia
    Posts
    1,859
    What's the name of an internet troll who posts really simple questions to annoy people on a forum? I read it in an article a while ago and I can't seem to find it.
    Fact - Beethoven wrote his first symphony in C

  6. #6
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    27,078
    You might be thinking of a help vampire, but that's a bit different from a troll.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  7. #7
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    37,421
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  8. #8
    Informer -Adrian's Avatar
    Join Date
    Jan 2013
    Posts
    802
    Quote Originally Posted by Above article
    Another key indicator for Help Vampires is the clearly stated but “impossible” question. These questions look reasonable on the surface, but in fact they are impossible to answer for a number of reasons. These questions include, for example, “How do I build a forum?” or “How can I make a chat site?”
    A painfully accurate description of what's seen here. Imo the article makes a strong case for altogether removing such people, even if it offers examples of how to help the afflicted.

Popular pages Recent additions subscribe to a feed

Tags for this Thread