@DennyD314

Как оценить сложность алгоритма?

Всем привет!
Решал задачу с https://www.hackerrank.com/challenges/climbing-the...
Вкратце: есть турнирная таблица (scores), где у игроков с одинаковыми очками одинаковое место в таблице и список очков у игрока(alice) после каждой игры. На выходе надо вернуть метро в турнирной таблице после каждой игры.
Сразу очевидным решением показалось

def climbingLeaderboard(scores, alice):
    return [sorted(set(scores + [ball]), reverse=True).index(ball) + 1 for ball in alice]


Но такой алгоритм оказался не оптимальным, так как некоторые тесты падали по таймауту. Сложность я оценил как O(len(scores) * len(alice))

Верным оказалось такое решение:

def climbingLeaderboard(scores, alice):
    res = []
    scores = sorted(set(scores), reverse=True)
    i = len(scores)
    for b in alice:
        while (i > 0) and (b >= scores[i-1]):
            i -= 1
        res.append(i + 1)
    return res


Как в таком случае посчитать сложность алгоритма ? scores и alice - списки разной длины scores > alice.

Также хотелось бы узнать ваше мнение по такому вопросу: такой навык, как нахождение оптимального алгоритма можно натренировать постоянным решением подобных задач ? Дело в том, что встретив такую задачу в реальной жизни, я бы никогда не подумал написать что-то кроме решения 1, и на данный момент, мне кажется, что решение большого количества таких задач это не изменило бы.
  • Вопрос задан
  • 1524 просмотра
Решения вопроса 1
Rsa97
@Rsa97
Для правильного вопроса надо знать половину ответа
Навык нахождения оптимального алгоритма можно натренировать решением любых задач в условиях ограничения каких-либо ресурсов. Скажем, для оптимизации по времени вашу задачу можно решить составлением ещё одного массива, где индексом будет количество очков, а содержимым элемента - позиция в таблице. Тогда задача будет решаться за линейное время O(n) за счёт увеличения расхода памяти.
Приведу пример на псевдокоде.
positions := array[0..max_scores] of 0
foreach of scores as score
  positions[score] := 1
position := 1
for i := max_scores to 0
  temp := position + positions[i]
  positions[i] := position
  position := temp
result := array[]
foreach of alice as score
  result[] := positions[score]
Ответ написан
Комментировать
Пригласить эксперта
Ответы на вопрос 1
@Teslaman
Поскольку здесь два вложенных цикла - сложность составляет О(n^2).
В первом случае все еще хуже, имеем три вложенных цикла - О(n^3). Изучите что значит нотация О большое и как с его помощью оценивать алгоритмы.
Поясню, при оценке с помощью О большого мы не оперируем конкретными значениями вроде len(alice). Нас интересует худший вариант, поэтому отбрасывается все малозначительное. Самая дорогая часть - циклы.
Примеры:
Один цикл - O(n)
Два невложенных цикла - всё ещё О(n)
Два вложенных цикла - уже O(n^2) и т.д.
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы