Pull to refresh

Comments 29

Насколько я помню эту задачку из "Конкретной математики", он не только выжил сам, но и поставил на правильное место своего товарища.

Рекурсивный алгоритм линейной глубины - не очень хорошая идея..

def josephus2(n, k):
    alive = [i for i in range(n)]
    i = 0
    while len(alive) > 1:
        i = (i + k - 1) % n
        alive.pop(i)
        n -= 1
    return alive[0]

Функция pop для списка в общем случае имеет линейную временную сложность O(n). Для связных список это время поиска нужного элемента, для реализации на основе массива - время сдвижки правой части.

Так что у вас квадратичный алгоритм, т.к. внутри цикла O(n) у вас операция O(n).

Квадратичный алгоритм, ага. Но код нагляднее, действительно.

Вы pop с remove не путаете? remove удаляет по значению, pop - по индексу.

PS по времени (машинному) я сравнил, у меня на порядок быстрее, но это ни о чем не говорит, конечно.

PPS В Питоне нет массивов....

Упс. O(1) только для pop(0) и pop(-1), оказывается. Тогда извиняюсь.

А почему извиняетесь? Вы, вроде бы, и не утверждали, что этот код имеет линейную сложность. И для моделирования он более естественно выглядит. Мне как раз с него и стоило бы начать, кажется.

За попытку утверждения, что pop(i) выполняется за О(1).

На самом деле, в голову приходит тогда два варианта - связанный список и чисто математическое решение. Сегодня поразмышляю.

Из списка можно удалять за O(1), да, но в нём нет индексации за O(1). Кажется, что уже при k=3простой формулы не знают.

Кстати, если не ошибаюсь, представленный в статье наивный алгоритм работает за O(k*n), потому что на одно убиение приходится k шагов.

На самом деле, на одно убийство может и больше k шагов уйти: ведь в массиве будет становиться всё больше и больше убитых (и пока мы найдём k-го живого, нам придётся пройти много индексов).

Действительно. Всё ещё хуже :)

k шагов на убийство можно сохранить, если вместо массива использовать связный список и выкидывать из него элементы.

Не совсем понимаю, почему 12й грохает 7го, хотя при ходе 12го "каждый второй" - это теоретически он сам?!

Вы ведь имеете в виду последнее убийство? Предпоследним убит нулевой. После этого идём по кругу и считаем: 7 — первый, 12 — второй, 7 — третий. Правильно?..

Тьфу-ты-ну-ты, ну ведь правда же 7ой убивает сам себя, как это я так тупанул то... ¯\_(ツ)_/¯

Тут очень простая рекурсия, можно заменить циклом, сначала посчитать для i = 1, 2, ... n

    public static int Josephus(int n, int k)
    {
        var result = 0;
        for (var i = 2; i <= n; i++)
            result = (result + k) % i;
        return result + 1;
    }

Вы тут никак не учитываете, что есть и уже убитые мятежники.

Конечно же учитываю result = (result + k) % i;. Просто рекурсия заменена циклом.

Sign up to leave a comment.

Articles