如何确定算法的内存和时间复杂度？

Question

我不擅长确定时间和内存复杂度，希望有人能帮助我。

这里有一个算法，但我不确定它的时间和内存复杂度是什么。

Function sample(k)
   IF k < 2
       Return 0
   Return 1 + sample(k/2)

它的时间和空间复杂度是多少，为什么？

谢谢

- user3138212

---

这个问题应该发到理论计算机科学Stack Exchange。 - Ezequiel Muns

不，它确实不是研究级问题。 - Bernhard Barker

Answer 1

确定时间和内存复杂度就相当于统计在运行算法时使用了多少这两种资源，并查看随着输入大小(在此情况下是k)的变化这些数量如何改变。

时间将由每个指令被评估的次数决定，空间将由需要计算解决方案的数据结构有多大决定。

在这种特定场景下，您正在查看一个递归算法，因此基本上涉及以下两点: 1) 进行了多少递归调用; 2) 每个调用所完成的工作量。

由于每次调用都会将输入减半，因此调用序列将类似于：

sample(k)       )
 sample(k/2)    )
  sample(k/4)   ) 
     ...        ) - n = number of calls 
    sample(4)   )
     sample(2)  )
      sample(1) )

这样每次递归调用时减半的方式将导致呈现出一个 对数 次数的调用。

n = log(k)

在每次调用中，我们在调用堆栈中存储一定数量的变量，并进行一定量的工作（操作）。这是因为在每次调用中，变量和比较/加法/除法的数量不随更大的k而增加。

总时间复杂度是调用次数乘以每次调用所做的工作量，因此：

time complexity = A*log(k) + B

对于一些常量A和B，它们反映了进行递归调用和比较/分割所需的实际时间成本。同样地：

space complexity = C*log(k) + D

对于递归的空间成本和变量存储，我们需要合适的常数C和D。

在这种分析中，我们主要关注渐进复杂度，也就是说，我们并不关心常数，因为它们反映了运行算法的机器的细节，我们真正想知道的是曲线的形状（随着k的增加）。如果您遵循使用大O符号编写复杂度的规则，您将得到以下结果：

space complexity = time complexity = O(log(k))

编辑：内存复杂度细节

如我之前所说，内存复杂度取决于需要多大的数据结构来计算解决方案，那么你可能会问：这个函数没有使用数据结构，为什么会使用 log(k) 的内存呢？

简短回答： 您需要存储 log(k) 种不同的参数 k 值，每次递归调用时都要存储一个值。

详细回答： 这里通过函数调用机制（我们通过递归利用）使用了一个隐式的数据结构，其名称为 调用栈。每次调用 sample(k) 时，都会创建一个新的堆栈帧，并将一些值推送到堆栈上：参数 k 的本地值、返回地址和其他与实现有关的信息。这样，每个递归调用形成一个在堆栈上的“层”，其中存储着它的本地信息。整个情况最终看起来像这样：

----------- < 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的值，希望避免混淆）

需要注意的主要是，由于有n = log(k)次递归调用，因此有n个这样的堆栈帧。每个堆栈帧具有恒定的大小，因此空间复杂度为O(log(k))。

- Ezequiel Muns

---

请注意，使用尾递归的方式，空间部分可以轻松消除，从而实现O(logk)时间和O(1)空间。 - RichardPlunkett

@EzequielMuns 感谢您的回答。我仍然不太确定空间复杂度为什么是log(k)。如果您能进一步解释一下，我将不胜感激。 - user3138212

@user3138212 请查看详细答案 :) - Ezequiel Muns

Answer 2

你真正关注的是log_2(k)，以2为底数的对数。要改变底数，必须乘以一个常数。由于我们无论如何都要乘以常数，因此O(log(n))、O(ln(n))和O(log_2(n))都是相同的。

那么为什么上述方法具有以2为底数的对数复杂度呢？每次调用时，你都将k除以2。如果你倒过来，每次调用时就会乘以2。乘以2是2^n，而log_2(n)恰好是其倒数。

也许画一个二叉树会有所帮助：一个有n个节点的树的高度为log_2(n)，一个高度为n的树有2^n个节点。

- user835611