我觉得我可以从教科书中给出的示例中很好地理解“大O”，但是一旦我不得不为自己编写的实际功能弄清楚了，就很茫然。谁能帮我计算和理解以下三个函数的大O和时间复杂度/空间复杂度？
基本上，这只是一个LeaderBoard类，并且页首横幅的格式如下：
{player_id: [average, [score1, score2, score3...]]...}
这是我的代码：
class LeaderBoard:
def __init__(self):
self.leaderboard = {}
def add_score(self, player_id, score):
if player_id in self.leaderboard:
self.leaderboard[player_id][1].append(score)
avg = sum(self.leaderboard[player_id][1])/len(self.leaderboard[player_id][1])
self.leaderboard[player_id][0] = avg
return avg
self.leaderboard[player_id] = [score,[score]]
return score
def top(self, no_of_top_players):
top_list = []
for key,value in sorted(self.leaderboard.items(),key=lambda e:e[1][0], reverse=True):
top_list.append(key)
return top_list[:no_of_top_players]
def reset(self, player_id):
if player_id in self.leaderboard:
self.leaderboard[player_id][0] = 0
self.leaderboard[player_id][1] = []
最佳答案
这是代码的（几乎）逐行分析，显示了（几乎）每一行的复杂性。要获得方法的总复杂度，通常需要采用该方法内部出现的最大复杂度。
def add_score(self, player_id, score):
"""
Time complexity of this method is 'O(k)', where 'k' is the number of scores that
the specified 'player_id' has.
"""
if player_id in self.leaderboard: # O(1) membership check in dict
player = self.leaderboard[player_id] # O(1) get item from dict
score_list = player[1] # O(1) get item from list
score_list.append(score) # O(1) list append
sum_score_list = sum(score_list) # O(len_score_list) list sum
len_score_list = len(score_list) # O(1) list length
avg = sum_score_list / len_score_list # O(1) int division
player[0] = avg # O(1) assignment
return avg # O(1) return
new_data = [score, [score, ]] # O(1) lists creation
self.leaderboard[player_id] = new_data # O(1) assigment
return score # O(1) return
def top(self, no_of_top_players):
"""
Time complexity of this method is 'O(n log n)', where 'n' is the number players.
"""
sorted_player_list = sorted( # O(n log n) list sort
self.leaderboard.items(),
key=lambda e: e[1][0], reverse=True)
top_list = [] # O(1) list creation
for key, value in sorted_player_list:
top_list.append(key) # O(n) list append n times
top_list = top_list[:no_of_top_players] # O(no_of_top_players) list slice
return top_list # O(1) return
def reset(self, player_id):
"""
Time complexity of this method is 'O(1)'.
"""
if player_id in self.leaderboard: # O(1) membership check in dict
player = self.leaderboard[player_id] # O(1) get item from dict
player[0] = 0 # O(1) assignment
player[1] = [] # O(1) list creation and assignment
希望这可以帮助您朝正确的方向开始，以便将来分析您的代码。
关于python - 需要帮助了解大O，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/54931017/