我想确定second_max函数的复杂度但我该怎么做，如何确定我的代码和任何其他代码的时间复杂度
from random import randint
import sys
from bigO import BigO
def r_array(r_i= 0,r_e = 100,step=10):
return [randint(r_i, r_e) for i in range(r_i, r_e, step)]
def second_max(arr):
n_max = -sys.maxsize
n_s_max = -sys.maxsize
for i in range(0, len(arr)):
if arr[i] > n_max:
n_s_max = n_max
n_max = arr[i]
elif (arr[i] < n_max and arr[i] > n_s_max):
n_s_max = arr[i]
return n_s_max
_lib = BigO()
cmplx = _lib.test(second_max, "")
array = r_array(step=20)
print(f"original array: {array}")
second_large_num = second_max(array)
print(second_large_num)
我认为我的代码(second_max)有0 (n)复杂度，但不确定。
我尝试了bigO模块，但它返回
for i in range(len(array) - 1):
TypeError: object of type 'int' has no len()
首先，bigO python模块只能估计时间复杂度。从理论上讲，程序是不可能"计算"的。所有可能算法的时间复杂度。这与停机问题类似。
所以不要依赖那个模块来计算时间复杂度。没有确定时间复杂度的方法总是有效的。对于一些复杂的、已知的算法，甚至还没有证据证明它们的时间复杂度是多少。
第二件要考虑的事情是𝑛是什么。在您的示例中，列表的大小似乎是𝑛。有时，虽然列表中数字本身的(最大)大小也可以考虑在内，因为(例如)两个数字的比较需要的时间取决于数字的(内存)大小，特别是当Python具有不受限制的整数大小时(请参阅计算复杂性)。在这里，我将假设数字的大小不是𝑛的一个方面，并且所有的比较操作可以被认为在0(1)时间复杂度内运行。
对于这段特定的代码，我们可以做一个简单的分析:只有一个循环访问arr列表的每个成员，并且循环体中的每个操作具有恒定的时间复杂度(这些操作都不依赖于列表的大小):
if arr[i] > n_max:
n_s_max = n_max
n_max = arr[i]
elif (arr[i] < n_max and arr[i] > n_s_max):
n_s_max = arr[i]
上面所有的行，如果它们被执行，时间复杂度为0(1)(同样，基于上述假设)。此外，循环条件和循环前的初始化具有恒定的时间复杂度。
这意味着总时间复杂度为0(𝑛)。
我假设O(n)中的n表示数组长度len(arr)，这是唯一合理的解释。
我认为我的代码(second_max)有0 (n)复杂度，但不确定。
可以小于O(n)吗?不，你有一个循环执行n次:
for i in range(0, len(arr)):
可以大于O(n)吗?没有:
- 在循环之外，你只有简单的赋值，每个都是
O(1)，执行一次，结果是O(1)-我们可以忽略它，因为我们已经有了O(n)部分。 - 在循环中，只有简单的比较、条件和赋值，每个都是
O(1)，最多执行n次。这导致O(n)。
所以，总的来说是O(n)。