python - 需要帮助了解大O
问题描述
我觉得我从教科书中给出的示例中很好地掌握了大 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
我希望这能让你在未来开始分析你的代码的正确方向。
推荐阅读
- java - 从包含周名和时间的字符串中解析时间
- php - 如果某些值未填写在表单中,则不会更新数据库
- java - 安装 Jython 以使用 PythonInterpreter
- android-studio - 当我尝试安装 Android Studio Emulator 时。我得到错误。我该如何解决这个问题
- python - 如何从使用 for 循环创建的嵌套列表中删除空格?
- regex - 为什么 VSCode 中的 `f(?=\=)` 正则表达式无效?
- javascript - 如何使用 rxjs 和 redux observable 实现 Promise 类型的场景?
- android - 为什么我在 android react native 的 Restful api 的 GET 请求中得到 html 响应作为数据?
- eclipse - 自动导出 eclipse python (pydev) 项目
- c# - 试图在统一 c# 中保存 xml 文件但得到一个空文件