5

I am asked to provide the asymptotic space and time complexity of the below algorithm in appropriate terms for an initial input number of arbitrary length (as distinct from a constant 12 digits).

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

This algorithm is apply for a number that has 12 digits, each digit is stored in the array d[] (so we have d[1], d[2],... d[12])

I figured out the time complexity is O(n) but how do I determine the space complexity?

4

1 回答 1

6

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

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

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

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

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

希望这可以帮助！

于 2013-09-15T22:57:26.680 回答