what is the meaning of O(1), O(n), O(n*n) memory?
Possible Duplicate:
Plain English explanation of Big O
Many times when time complexity of a algorithm is talked about, memory also comes into account. I want to know what is the meaning of big-O(1), big-O(n), big-O(n*n) memory?
And how it is related to time complexity?
As xmoex said:
o(1) constitutes a constant memory usage. So amount of input is inconsequential.
o(n) constitutes a linear memory usage. So more input means linearly more memory.
o(n*n) constitutes a quadratic memory usage. So more input means quadratically more memory (x^2 on average.
This measure of memory complexity in most cases is completely independent to the measure of time complexity. For computer algorithms it is important to know how the algorithm will manage both of these complexities to decide the quality of the algorithm. However both must be calculated separately. One may be more important than the other depending on your use cases and circumstances for the problem.
o(1) means constant average memory use, regardless the size of your input
o(n) means if you have n element you are processing, your average memory need grows linear
o(n*n) means if you have n elements you are processing, your average memory need will grow quadratic
there's a wiki article about the so called big o notation (covering little o as well...)
I am not sure if you mean big-O or little-O here, but I am going to answer more generally.
It means the same thing for memory as it does for time. If a function grows in memory O(1) then it uses a constant amount of memory regardless of the input size. If a function grows in O(n) it uses a linear amount, and O(n*n) it uses a quadratic amount.
链接地址: http://www.djcxy.com/p/6744.html上一篇: 两个for循环的时间复杂度