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

Question

这是我学校过去一年中期论文的问题.下面附有一张图,用于显示机器人如何从同一张纸上移动.我的担忧在橙色部分中说明.

基本上,只要机器人遇到左侧未看到的网格方块,机器人就会向前移动并向左转.

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

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

说明实施时间和空间的增长顺序,并解释您的答案.

这些是markscheme中建议的答案.

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)我是否正确地推断形成元组的时间复杂度的推导似乎是每次递归/迭代之后更新元组的长度的总和.

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

我看到了一个关于字符串而不是元组的相关帖子,在这种情况下,time = 1 + 2 + ... n = n ^ 2,这支持我的推理.

Python中字符串连接的时间复杂度

2)对于涉及切片/连接的递归函数的空间复杂度,空间等于它们的时间,在这种情况下是O(n ^ 3),这是正确的.我对这种情况的解释是:由于有n个递归占用了堆栈上的空间,并且每次递归都会形成一个长度为n ^ 2的新元组,这是由连接形成的(这里没有切片),空间将是O(n*N ^ 2).

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

Answer 1

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

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

• 创建字符文字的时间复杂度为 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对于 i->n，以 n 的大小重新构造。空间被重用，最多为O(n) space。所有 n 次迭代都会消耗时间，即 O(n*n) = O(n^2) 时间。
• seq在所有 n 次迭代中 与 n 元组连接。空间被重用，最多 O(n*n) = O(n^2) space。所有 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 元组连接。空间被重用，因为每个return值都是在递归后构造的，最多 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)。
• 该yield from ... range(i)循环的时间为 O(n)，空间为 O(1)。空间重用将其保留为O(1) space。重复 n 次给出 O(n*n) = O(n^2) 时间。
• 通过O(n^2 * 1) = O(n^2) space一次性连接所有结果。tuple

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