Нужна помощь в понимании большой O - PullRequest
Новая
       94

Нужна помощь в понимании большой O

0 голосов
/ 28 февраля 2019

Мне кажется, что я хорошо разбираюсь в больших 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] = []

1 Ответ

0 голосов
/ 28 февраля 2019

Вот (почти) построчный анализ вашего кода, показывающий сложность (почти) каждой строки.Чтобы получить полную сложность метода, вы обычно берете наибольшую сложность, которая проявляется внутри этого метода. 

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

Я надеюсь, что это поможет вам в правильном направлении анализировать ваш код в будущем.

...