python - 根据我的代码确定时间复杂度并进行一些修改

Question

我对我的代码中的时间复杂度有疑问。我试图引用一些网站和教程以及 stackoverflow 的解释，但仍然无法理解我们如何计算或确定代码的时间复杂度。如果可能的话，是否可以检查我的代码并根据它进行解释，并提供一些简单的示例或链接(我还在学习)来研究它。

我试过这段代码并尝试提交但是时间复杂度很高所以没有被接受。有没有办法降低时间复杂度？

问题来自this link

def large_element(array):
    stack = []
    took = False
    for i in range(len(array)):
        s_integer = array[i+1:]
        if i != len(array)-1:
            for ii in range(len(s_integer)):
                if array[i] < s_integer[ii] and took == False:
                        stack.append(s_integer[ii])
                        took = True
                elif array[i] > s_integer[ii] and took == False and ii == len(s_integer)-1:
                        stack.append(-1)
                        took = True
            took = False
        else:
                stack.append(-1)
    return stack

import time
start_time = time.time()
integer = [4,3,2,1]
print(large_element(integer))

我目前的理解是，我的代码有 2 次 for 循环来循环每个元素，所以这将是 O(n2)？

顺便说一句，输出是:[-1, -1, -1, -1]

Answer 1

执行此操作的一种简化但有效的方法是为每一行代码指定一个成本并计算该行运行了多少次。当然，您应该保持代码行简单，这样才有意义。

一行的成本不需要非常精确，因为在大 O 表示法中常量会被忽略。

简单的例子:n 等于列表的大小 x

def print_list(x : list):
    for i in x:          # cost = c1; count = n
        print(i)         # cost = c2; count = n
    print('done')    # cost = c3; count = 1

for 所在的行被调用了 n 次，因为虽然 for 只执行了一次，但是决定循环是否继续的比较进行了 n 次。

这个函数的时间复杂度等于每行成本与重复次数的乘积之和:

复杂度 = c1×n + c2×n + c3×1 = O(n)

在这种情况下，成本被忽略，因为它们恰好是常量。但是，指令的成本可能取决于输入的大小，大多数情况下是在指令调用子例程时。

此外，在我给出的示例中，每条指令最多被调用 n 次，但在嵌套循环等地方，此计数可能是 n²、log(n) 等。

我建议阅读 Cormen、Leiserson、Rivest 和 Stein 合着的《算法导论》一书。这种解释主要基于书中第一章的内容。