I am not good at determining time and memory complexities and would appreciate it if someone could help me out.
I have an algorithm, here and I am not sure what its time and memory complexities would be.
Function sample(k)
IF k < 2
Return 0
Return 1 + sample(k/2)
What is its time and memory complexity and why?
Thanks
Determining time and memory complexities amounts to counting how much of these two resources are used when running the algorithm, and seeing how these amounts change as the input size (k in this case) changes.
Time is going to be determined by how many times each of the instructions are evaluated, and space will be determined by how large the data structures involved need to get to compute the solution.
In this particular scenario, you're looking at a recursive algorithm, so basically this involves counting 1) how many recursive calls are made and 2) how much work is done for each of these calls.
Since the input is halved with each call, the sequence of calls will look something like this:
sample(k) )
sample(k/2) )
sample(k/4) )
... ) - n = number of calls
sample(4) )
sample(2) )
sample(1) )
Halving at each recursive call in this way will lead to a logarithmic number of calls.
n = log(k)
At each call we are storing a constant number of variables in the call stack, and doing constant amount of work (operations). This stems from the fact that the number of variables and the number of comparisons/additions/divisions in each call does not get bigger with bigger k.
The total time complexity is the number of calls multiplied by the amount of work done in each call, thus
time complexity = A*log(k) + B
For some constants A and B which reflect the actual time cost of doing a recursive call and doing comparisons/divisions respectively. Similarly:
space complexity = C*log(k) + D
For suitable constants C and D for space cost of recursion and variable storage respectively.
Now in this kind of analysis we care mostly about the asymptotic complexity, that is we don't really care about the constants because they reflect details about the machine which is running the algorithm, and we really want to know the shape of the curve (as k gets bigger). If you follow the rules of writing complexity using Big-Oh notation you'll arrive at the result:
space complexity = time complexity = O(log(k))
As I said before, memory complexity is determined by how large the data structures need to get to compute a solution, so you may ask: there are no data structures being used in this function, so where is the log(k) memory going?
The short answer: You have to store log(k) different values of the parameter k, one for each recursive call.
The detailed answer: there is an implicit data structure being used here by the mechanism of function calling (which we exploit via recursion) and its name is the call stack. Each time sample(k) is called, a new stack frame is created and a number of values are pushed onto the stack: the local value of the parameter k, the return address, and other implementation dependent things. In this way each recursive call forms a 'layer' on the stack where its local information is stored. The whole picture ends up looking something like this:
----------- < top of stack
| k = 1 |
| ... | < stack frame for sample(1)
|---------|
| k = 2 |
| ... | < stack frame for sample(2)
|---------|
...
|---------|
| k = p/2 |
| ... | < stack frame for sample(p/2)
|---------|
| k = p |
| ... | < stack frame for sample(p)
|---------|
| | < stack frame for main() or whatever
initially called sample(p)
(we don't count this one)
(I've distinguished here the initial parameter value p from the value of k at each recursive call to avoid confusion, hopefully)
Main thing to note is, as there are n = log(k) recursive calls, there are n such stack frames. Each stack frame has constant size, and thus the space complexity is O(log(k)).
你真的在看 log_2(k)，以 2 为底的对数。要改变底数，你必须乘以一个常数。而且由于我们无论如何都要乘以常数，所以 O(log(n))、O(ln(n)) 和 O(log_2(n)) 都是相同的。
那么为什么上述方法具有以 2 为底的对数复杂度呢？每次通话时，您都将 k 分成两半。如果你倒退，你每次调用都会乘以 2。乘以 2 是 2^n，而 log_2(n) 正好是它的倒数。
如果绘制二叉树可能会有所帮助：具有 n 个节点的树的高度为 log_2(n)，高度为 n 的树具有 2^n 个节点。