试图在 Python 的这一点中找到 T(n) 函数和复杂度

Question

def wum(aList):
    a = 7
    b = 5
    n = len(aList)
    for i in range(n):
        for j in range(n):
            a = i * a
            b = j * j
            w = i * j
            v = i + w
        x = v * v
        for k in range(n):
            w = a * k + 23
            v = b * b
        a = w + v

我有 T(n) = 2n + 6n^2 复杂度 O(n^2)，这样对吗？求助！

Answer 1

我总是觉得给 T(n) 一个准确的值有点困难，因为很难定义 1 在那里意味着什么。但是假设每个分配都是 1（不管发生什么样的计算），那么总的 T(n) 将如下所示：n * (6n + 2) + 3.

但在大 O 表示法中，即 O(n²)，是的。您可以很容易地看到，因为您有两个嵌套循环级别，都在 n.

顺便说一句。你的功能可能是你的导师或其他人的例子，但它确实是一个糟糕的例子。您可以轻松地将逻辑修改为线性并产生相同的结果：

a = 7
b = 5
n = len(aList)
for i in range(n):
    a *= i ** n # `a` is multiplicated `n` times by (constant) `i`
    b = (n - 1) ** 2 # at the end of the loop, `j` is `(n - 1)`
    v = i + (i * b) # at the end of the loop, `w` is `i * b`
    x = v * v
    w = a * (n - 1) + 23 # at the end of the loop, `k` is `(n - 1)`
    v = b ** 2 # `b` (and as such `v`) is never changed in the loop
    a = w + v

而且由于没有任何东西使用列表的任何值，您实际上也可以在恒定时间内进行这些计算（我将把它留给您练习；））。

最后，您可能会争辩说，由于该函数没有 return 任何东西，也没有改变输入列表，因此该函数是一个很大的 NO-OP，因此可以用一个什么都不做的函数：

def wum(aList):
    pass

试图在 Python 的这一点中找到 T(n) 函数和复杂度

Trying to find the T(n) function and complexity in this bit of Python

python

big-o

function