如何确定算法的内存和时间复杂度？ [英] How to determine memory and time complexity of an algorithm?
问题描述
我不擅长确定时间和内存的复杂性，如果有人可以帮助我，我将不胜感激。
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?
谢谢
推荐答案
确定时间和内存复杂度等于计数，在运行算法时要使用这两种资源中的多少，并查看这些数量随输入大小（ k ）如何变化） 变化。
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.
在这种特殊情况下，您正在查看一种递归算法，因此基本上，这涉及计数1）进行了多少次递归调用和2）完成了多少工作每个电话。
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)
在每次通话中在调用堆栈中存储数量为 constant 的变量，并进行固定数量的工作（操作）。这是由于以下事实：每次调用 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
对于一些常数A和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
分别针对递归和变量存储的空间成本使用合适的常数C和D。
For suitable constants C and D for space cost of recursion and variable storage respectively.
现在，在这种分析中，我们主要关心渐近复杂性，也就是说，我们实际上并不关心常量，因为它们反映了运行机器的详细信息。算法，我们真的很想知道曲线的形状（随着 k 变大）。如果遵循使用Big-Oh表示法编写复杂性的规则，则会得到以下结果：
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))
编辑：内存复杂度详细信息
如我之前所说，内存复杂度由计算解决方案所需的数据结构大小决定，因此您可能会问：没有数据该函数中使用的结构，那么log（k）的存储空间在哪里？
Memory complexity details
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?
简短的答案：您必须存储 log（k）参数 k 的不同值，每个递归调用一个。
The short answer: You have to store log(k) different values of the parameter k, one for each recursive call.
详细的答案：：这里有一个隐式数据结构被函数调用机制使用（我们通过递归利用），其名称为 调用堆栈 。每次调用 sample（k）时，都会创建一个新的堆栈框架，并将许多值压入堆栈：参数
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)
（我在这里将初始参数值 p 与 k 希望在每次递归调用时都能避免混淆）
(I've distinguished here the initial parameter value p from the value of k at each recursive call to avoid confusion, hopefully)
主要要注意的是，因为 n = log（k）递归调用，有 n 这样的堆栈框架。每个堆栈帧具有恒定的大小，因此空间复杂度为 O（log（k））。
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)).
这篇关于如何确定算法的内存和时间复杂度？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
