确定此函数的最坏情况时间复杂度？

Question

我目前正在研究 Richard Hammack 的 'Book of Proof' 中的集合，并且我正在尝试将集合实现为幂（更具体地说，是集合的笛卡尔幂）。示例如下：
假设我设置了 A = {0, 1}，那么
A² = {0, 1} x {0, 1} = {(0, 0), (0, 1), (1, 0), (1, 1)}

我成功实现了一个通用函数，可以将集合提升到我指定的任何幂。代码如下：

def add_to_tuple(tup, a):
    tup = list(tup)
    tup.append(a)
    return tuple(tup)


def multiply(A, B):
    return_set = []
    for a in A:
        for b in B:
            if type(a) is tuple and type(b) is tuple:
                return_set.append(a + b)
            elif type(a) is not tuple and type(b) is tuple:
                return_set.append(add_to_tuple(b, a))
            elif type(a) is tuple and type(b) is not tuple:
                return_set.append(add_to_tuple(a, b))
            else:
                return_set.append((a, b))
    return return_set


def set_to_power(finite_set, power):
    if power == 1:
        return finite_set
    else:
        return multiply(finite_set, set_to_power(finite_set, power - 1))

a = [0, 1]
print(set_to_power(a, 2))

下面的输出是：[(0, 0), (0, 1), (1, 0), (1, 1)]
我正在尝试计算 set_to_power 的时间复杂度，但我不确定它是否为 n²。

Answer 1

先来看看multiply：您有 2 个没有中断或 returns 的嵌套 for 循环，因此无论其中包含什么，都将执行 len(A) * len(B) 次。 add_to_tuple 取决于元组的大小；我稍后再讲，现在让我们假设 power = 2 的基本情况，所以 add_to_tuple 不会发生。在那种情况下，它们是常数，所以除了 for 循环之外的所有东西都在 O(1) 时间内。所以是的，你的乘法将运行在 O(n^2) 时间内获得幂 2.

当我们到达 set_to_power 函数时，问题就开始了 - 它有 2 个参数，这两个参数都会影响函数的复杂性。所以它肯定不会是 O(n^2) - 我们必须以某种方式考虑功率变量。首先，你的 add_to_tuple 是 O(i) （90% 确定，虽然我不确定 list() 和 tuple()) 的内部工作原理幂变量项。所以这已经意味着 multiply 中的每个运行将占用 O(i*(n^2))。然后你触发了 i 次，每次在其中一个集合中有 n 倍的元素。我 thiiiiink 它会像 ~ O(i^2 * n * n^i) （i 大致是 power-1，但我不确定它与 Big-O 符号有什么关系。）

Answer 2

让我们一一看看所有的功能-

`1.add_to_tuple(tup, a)`

这个函数是 O(n) 其中 n 是元组的长度。在函数中，tup = list(tup) 是 O(n) 与 final tuple(tup) 相同，其中 tup 是列表。在 python 中，tuple <--> list 之间的转换是 O(n)，因为 python 需要复制 list/[ 中的所有项目=20=] 给另一个。因此，在列表中添加成员时使用 list，最后您可以根据需要将 list 转换为 tuple。

`2.multiply(A, B)`

这是 O(len(A) * len(B) * O(add_to_tuple)，因为我们正在遍历 A 和 B 中的所有项目，然后为每个项目调用 add_to_tuple = O(n^3) 其中 n 是集合的长度 (A)

`3.set_to_power(finite_set, power)`

假设 power 是 k，finite_set 的初始长度是 n。我们将调用 multiply 函数 k 次，在每次调用 multiply 函数期间，结果 finite_set 将成为先前大小的 n 倍. 例如[0, 1] 和 [0, 1, 2] 为 finite_set

>>> set_to_power([0, 1], 1)
[0, 1]
>>> set_to_power([0, 1], 2)
[(0, 0), (0, 1), (1, 0), (1, 1)]
>>> set_to_power([0, 1], 3)
[(0, 0, 0), (0, 1, 0), (1, 0, 0), (1, 1, 0), (0, 0, 1), (0, 1, 1), (1, 0, 1), (1, 1, 1)]
>>> set_to_power([0, 1, 2], 1)
[0, 1, 2]
>>> set_to_power([0, 1, 2], 2)
[(0, 0), (0, 1), (0, 2), (1, 0), (1, 1), (1, 2), (2, 0), (2, 1), (2, 2)]
>>> set_to_power([0, 1, 2], 3)
[(0, 0, 0), (0, 1, 0), (0, 2, 0), (1, 0, 0), (1, 1, 0), (1, 2, 0), (2, 0, 0), (2, 1, 0), (2, 2, 0), (0, 0, 1), (0, 1, 1), (0, 2, 1), (1, 0, 1), (1, 1, 1), (1, 2, 1), (2, 0, 1), (2, 1, 1), (2, 2, 1), (0, 0, 2), (0, 1, 2), (0, 2, 2), (1, 0, 2), (1, 1, 2), (1, 2, 2), (2, 0, 2), (2, 1, 2), (2, 2, 2)]

所以总复杂度将为 -

First call to multiply - O(n^3) +
Second call to multiply, the new finite_set will be of length n*n - O((n*n)^3) + 
Third call to multiply - O((n*n*n)^3) + ... k times

您的解决方案 O(N^3k)。

您可以将复杂性降低到 O(N^2k)，方法是修复 add_to_tuple 中的转换并使用 lists 来代替 append 的分摊 O(1) 复杂性] 操作。

附带说明一下，该问题的最佳解决方案的复杂度为 O(k*N^k)，因为结果集中将有 N^K 个项目，每个项目的长度为 k。您生成的基本上是所有长度为 k 的项目，它们是给定初始集合的排列，其中每个元素都可以重复（例如，请参见上面 set_to_power([0, 1, 2], 3) 的输出）。我们可以从一个元素 [0, 0, 0] 开始，然后将其添加到我们的答案中，然后在每一步中不断增加需要增加的最后一位数字

e.g. [0, 0, 0] -> [0, 0, 1] -> [0, 0, 2] -> [0, 1, 0] -> [0, 1, 1] ...

每一步都可以是 O(k)，因为您需要创建先前列表的副本，然后在 O(1) 时间内将其修改为下一个数字。这将导致 O(k*N^k) 解决方案。

确定此函数的最坏情况时间复杂度？

Determining worst-case time-complexity of this function?

python

time-complexity

big-o

`1.add_to_tuple(tup, a)`

`2.multiply(A, B)`

`3.set_to_power(finite_set, power)`