Python:创建大小为 n^2 的元组的时间和空间复杂度

Question

这是我学校过去一年的期中论文中的一个问题。下面附上一张图表，显示机器人将如何移动，来自同一张纸。我的顾虑在橙色部分说明。

基本上，只要遇到左侧未访问的网格方 block ，机器人就会向前移动并向左转。

给机器人横穿 3 号网格的指令序列是:('F', 'T', 'F', 'T', 'F', 'F', 'T', 'F', 'F', 'T', 'F', 'F', ' F')其中“F”表示向前移动一格，“T”表示向左转 90 度。请注意，最后一条指令导致机器人退出网格。函数 gen_seq 将网格的大小作为输入，并返回机器人横穿网格的指令序列。指令序列是一个包含字符串“F”和“T”的元组，表示前进和转向命令。

提供函数 gen_seq 的递归或迭代实现。提示:Recall int 可以与 tuple 相乘。

根据实现的时间和空间说明增长顺序，并解释您的答案。

这些是评分方案中建议的答案。

def gen_seq(n): # recursive
    if n == 1:
        return ('F',)
    else:
        side = ('T',) + (n-1)*('F',)
        return gen_seq(n-1) + side + side + ('F',)

def gen_seq(n): # iterative
    seq = ('F',)
    for i in range(2, n+1):
        side = ('T',) + (n-1)*('F',)
        seq += side + side + ('F',)
    return seq

时间:O(n^3)。在每个函数调用(递归)或循环(迭代)中，都会创建一个新的元组，其长度为螺旋的每个“层”的路径长度。由于螺旋的长度为n^2，并且有n次函数调用或循环运行n次，所以总时间为n^2*n = O(n3)。换句话说，它是平方和:1^2+2^2+3^2+: : :+n^2 = O(n^3)

空间:O(n^2)。一天结束时，将创建并返回一个大小为 n^2 的新元组。

1)Am I right to infer that the derivation for time complexity of forming a tuple seems to be sum of length of updated tuple after every recursion/iteration.

如果我想形成一个大小为 n^2(拉直螺旋的大小)的元组，首先必须形成 1^2，然后是 2^2 ... n^2，从而得出上述平方和。

我看到一篇关于字符串而不是元组的相关帖子，在这种情况下时间= 1+2+…n=n^2，这支持了我的推断。

Time complexity of string concatenation in Python

2)Is it correct for me to say for space complexity of recursive functions that involve slicing/concatenation, space equal to their time, in this case O(n^3). My explanation for this case would be: Since there are n recursions that takes up space on the stack, and each recursion a new tuple of length n^2 is formed from concatenation (no slicing is seen here), space would be O(n*n^2).

我还认为建议的 O(n^2) 空间仅适用于没有观察到堆栈帧且空间中仅包含最终元组 (n^2) 的长度的迭代解决方案。

Answer 1

TLDR:您的时间复杂度是正确的，尽管您的递归 gen_seq 的 O(n^3) 空间过于悲观(它仍然更加浪费)。请注意，最佳静态解决方案是 O(n^2)，因为这是答案的大小。如果不需要静态答案，空间复杂度可以降低到 O(1)。

---

让我们从建立一些基本的复杂性开始。以下内容适用于时间和空间复杂度:

• 创建字 rune 字的复杂度为 O(1)。
• 创建一个大小为 n 的元组是 O(n)。
  • 创建空元组或单元素元组的复杂度为 O(1)。
• 连接两个长度为 n 和 m 的元组是 O(n+m)。
  • 连接两个长度为 n^2 和 m 的元组，它是 O(n^2+m) = O(n^2)。

---

迭代:

def gen_seq(n): # iterative
    seq = ('F',)
    for i in range(2, n+1):
        side = ('T',) + (i-1)*('F',)  # note: `i-1` instead of `n-1`
        seq += side + side + ('F',)
    return seq

复杂性的关键点是:

• range(const, n+1) 循环是O(n) 时间 复杂度和O(1) 空间。
• side 被重新构建，大小为 n for i->n。空间被重用，最大 O(n) 空间。所有 n 次迭代都消耗时间，O(n*n) = O(n^2) 时间。
• seq 在所有 n 次迭代中与 n 元组连接。空间被重用，最大 O(n*n) = O(n^2) 空间。所有 n 次迭代都消耗时间，O(n*n^2) = O(n^3) 时间。

最大的复杂性获胜，因此迭代使用 O(n^2) 空间和O(n^3) 时间。

---

递归:

def gen_seq(n): # recursive
    if n == 1:
        return ('F',)
    else:
        side = ('T',) + (n-1)*('F',)
        return gen_seq(n-1) + side + side + ('F',)

复杂性的关键点是:

• 递归从 n->1 开始重复，意味着 O(n) 时间。
• side 被重新构建，大小为 n。空间 未被重用 ，因为每个 side 都是在 递归之前构建的，最大 O(n*n) = O( n^2) 个空格。所有 n 次迭代都消耗时间，时间为 O(n*n) = O(n^2)。
• return 值在所有 n 次迭代中与 n 元组连接。空间被重用，因为每个返回值都是在递归之后构造的，最大 O(n*n) = O( n^2) 个空格。所有 n 次迭代都消耗时间，O(n*n^2) = O(n^3) 时间。

最大的复杂性获胜，因此迭代使用 O(n^2) 空间和O(n^3) 时间。

---

时间复杂度的限制是每个步骤的结果必须在下一步中重复。在 Python 中，这可以使用生成器来规避 - 这允许您返回中间结果并继续生成更多结果:

def gen_seq(n):
    yield 'F'
    for i in range(1, n):
        yield 'T'
        yield from ('F' for _ in range(i))
        yield 'T'
        yield from ('F' for _ in range(i))

seq = tuple(gen_seq(m))

复杂性的关键点是:

• range(n) 循环是O(n) 时间 复杂度和O(1) 空间。
• ...range(i) 循环的 yield 是 O(n) 时间和 O(1) 空间。空间重用将其留在 O(1) 空间。重复 n 次得到 O(n*n) = O(n^2) 时间。


• 一次通过元组连接所有结果是 O(n^2 * 1) = O(n^2) 空间。

最大的复杂性获胜，因此迭代使用 O(n^2) 空间和 O(n^2) 时间。如果不存储直接使用结果，只占用O(1)的空间。