如何减少给定Python代码的执行时间?

Question

这里的疑问语句是:

我们有一个动物列表，其中第i只动物包含4个项目(index, a, b, c)。最初，动物0是最前面的，而其他动物1排在队列的前面，动物n - 1排在后面。排在队伍前面的动物将向国王发起挑战，力量更大的动物将赢得战斗。胜者为王，败者只能排在队伍的后面。

连续3次获胜的动物将被加冕为整个动物园的统治者。每只动物的力量取决于它连续赢得多少次战斗。动物i的实力a是连续赢0场，b是连续赢1场，c是连续赢2场。一开始，每个人都有0连胜。

对于所有动物，a>b和c>b。此外，a、b、c的值是不同的(所有3n个值都是两两不同的)。

我创建的函数可以工作，但是函数的时间复杂度有一个问题。

功能:

def competition(arr):
fights = 0
wins = 1
strength_k = arr[0][1]
while wins != 4:
king = 0
strength_k = arr[0][wins]
challenger = 1
strength_c = arr[1][1]
if strength_k > strength_c:
wins += 1
arr.append(arr[1])
arr.pop(1)
else:
wins = 2
arr.append(arr[0])
arr.pop(0)
fights += 1
if fights >= 3 and arr[0][0] == 0:
if arr[1][0] == 1:
return "-1 -1"
return f"{arr[0][0]} {fights}"

，其中arr看起来像:

[[0, 5, 1, 2], [1, 10, 8, 11], [2, 9, 0, 3], [3, 7, 4, 6]]

该函数将返回新的国王索引以及所进行的战斗数量。

此特定arr的示例输出将为"-1 -1"因为动物们会无休止地争斗，没有任何结果。

注意:

我认为我的终止有一个问题，当国王再次为0而挑战者为1时，我终止了循环(没有结果)。

谁能帮我减少相同的时间复杂度?

Answer 1

查看代码中的注释以获得简短的解释:

def competition(arr):
str_k = 1  # Start by comparing strength "a"
fights = 0
winners = []
while True:
j = 1
while arr[0][str_k] >= arr[j][1]:
fights += 1
winners.append(arr[0][str_k])
str_k += 1  # Increment strength everytime animal wins
j += 1  # Fight the next animal
if str_k > 3:  # 3 consecutive wins = King
return f"King of the zoo: {arr[0][0]} with {fights} fights"
fights += 1
if arr[j][1] in winners:  # If the winner animal has already won before and was NOT crowned king and won AGAIN, then we are repeating the cycle thus terminate
return "-1 -1"
winners.append(arr[j][1])
str_k = 2  # Start from strength "b" since it already won once
temp = arr[0]
arr[0] = arr.pop(j)  # Put winner animal in front
arr.append(temp)  # Send losing animal to the back

print(competition([[0, 5, 1, 2], [1, 10, 8, 11], [2, 9, 0, 3], [3, 7, 4, 6]]))