根据我的代码确定时间复杂性并进行一些更改

Question

我对代码中的时间复杂性有一个疑问。我试图参考许多站点和教程以及堆叠的说明，但仍然无法理解我们如何计算或确定代码的时间复杂性。如果可能的话，可以检查我的代码并基于它进行解释，并提供一些简单的示例或链接(我仍在学习(来研究它。

我尝试了此代码并尝试提交它，但是时间复杂性很高，因此不接受。有没有办法减少时间复杂性？

问题来自此链接

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次循环循环每个元素，因此这将是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，但比较决定是否应继续进行循环。

此功能的时间复杂性等于每行成本的产物的总和及其重复的次数：

复杂度= C1×N C2×N C3×1 = O(N(

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

另外，在我给出的示例中，每个指令最多称为n次，但是在嵌套循环之类的地方，该计数可能为n²，log(n(等。

我建议您阅读Cormen，Leisoserson，Rivest和Stein的算法简介。这种解释主要是基于书中在第一章中所说的。