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

Question

[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, и на данный момент, мне кажется, что решение большого количества таких задач это не изменило бы.

Answer 1

[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]

Answer 2

[Teslaman]

Поскольку здесь два вложенных цикла - сложность составляет О(n^2).
В первом случае все еще хуже, имеем три вложенных цикла - О(n^3). Изучите что значит нотация О большое и как с его помощью оценивать алгоритмы.
Поясню, при оценке с помощью О большого мы не оперируем конкретными значениями вроде len(alice). Нас интересует худший вариант, поэтому отбрасывается все малозначительное. Самая дорогая часть - циклы.
Примеры:
Один цикл - O(n)
Два невложенных цикла - всё ещё О(n)
Два вложенных цикла - уже O(n^2) и т.д.

Comments

[DennyD314]

Это не так. Почему тут будет n^2 ?? Что такое n ? Это длина массива. n^2 был бы если бы был цикл и вложенный цикл по 1 массиву длиной n. А насчет n^3 в первом варианте - первый цикл по alice * index(), который выполняется за O(len(scores))

[Teslaman]

DennyD314, n - это несколько абстрактная штука, обозначающая количество операций, которые выполнит алгоритм в худшем случае. В данном случае, за n можно принять len(scores).
Если взять len(scores) за n - то мы получим О(n^2), поскольку на каждую итерацию верхнего цикла for, мы проходим по всей длине scores в цикле while.

В первом случае Вы правы, я ошибся. Слева 3 цикла, но выполняются они последовательно.
Получается такая структура:

Цикл for:
    Цикл set
    Цикл sorted
    Цикл index

Двойная вложенность = O(n^2)

Собственно, хотя сложность одинаковая, во втором случае на один цикл меньше.
Чтобы понять это нужно знать что такое О-большое, для чего оно нужно и как его считать.

[DennyD314]

Teslaman, Не думаю, что вы правы. n - не "Абстрактная штука", а размерность входных данных.
В любом случае, спасибо за комментарий, благодаря вашему псевдокоду я понял, что в первом случае сложность для n=len(scores) и m=len(alice) будет O(n * log n * m) так как сложность sorted O(n * log n), то есть больше чем поиска по индексу, тогда как сложность второго варианта O(m * n)

[Teslaman]

DennyD314, оценка сложности алгоритма не является вычислением количества итераций. Как вы сами написали, N - это размерность входных данных. Но это просто абстрактная размерность последовательности. Нет никакого смысла принимать последовательность одного размера за N, а другого - за M, поскольку мы не оперируем конкретными числами. O-большое вообще не об этом.
Таким образом O(m * n) - некорректная запись, правильно: O(n * n) или O(n^2).