该算法在数组上循环的空间复杂度

Question

我被要求为任意长度的初始输入数字（与常量 12 位数字不同）以适当的术语提供以下算法的渐近空间和时间复杂度。

1 for i = 2 to 12
2     if d[i] == d[i-1]
3        d[i] = (d[i] + 3) mod 10

该算法适用于具有 12 位数字的数字，每个数字都存储在数组中d[]（因此我们有d[1], d[2],... d[12]）

我想出了时间复杂度，O(n)但是如何确定空间复杂度？

Answer 1

通常，为了测量空间复杂度，您需要查看需要多少额外空间来保存执行代码所需的所有信息。挑战在于您经常可以在代码执行的整个生命周期中重用空间。

在这种情况下，代码需要额外的空间来存储

• 循环中临时计算的值，
• i 的值，和
• 程序计数器等杂项数据。

其中后两个占用 O(1) 空间，因为只有一个 i 和用于辅助数据（如堆栈指针等）的常量空间。那么第一个呢？好吧，循环的每次迭代都需要 O(1) 空间来存储临时变量，但请注意，这个空间可以重用，因为在每次循环迭代完成后，这些临时变量的空间不再需要，可以在下一次重用迭代。因此，所需的总空间仅为 O(1)。

（注意……你确定时间复杂度是 O(n) 吗？请注意，无论数组有多大，迭代次数都是一个常数。）

希望这可以帮助！