Comments 29
Насколько я помню эту задачку из "Конкретной математики", он не только выжил сам, но и поставил на правильное место своего товарища.
Рекурсивный алгоритм линейной глубины - не очень хорошая идея..
Для небольших k это дело оптимизируется до O(k * ln(n))
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 В Питоне нет массивов....
А за какое время, на Ваш взгляд, работает pop?
Упс. O(1) только для pop(0) и pop(-1), оказывается. Тогда извиняюсь.
А почему извиняетесь? Вы, вроде бы, и не утверждали, что этот код имеет линейную сложность. И для моделирования он более естественно выглядит. Мне как раз с него и стоило бы начать, кажется.
www.youtube.com/watch?v=wWQ9YdreY9c
Кстати, если не ошибаюсь, представленный в статье наивный алгоритм работает за O(k*n), потому что на одно убиение приходится k шагов.
Вы имеете в виду первый алгоритм?
На самом деле, на одно убийство может и больше k шагов уйти: ведь в массиве будет становиться всё больше и больше убитых (и пока мы найдём k-го живого, нам придётся пройти много индексов).
Не совсем понимаю, почему 12й грохает 7го, хотя при ходе 12го "каждый второй" - это теоретически он сам?!
Тут очень простая рекурсия, можно заменить циклом, сначала посчитать для 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;
}
Собеседование по алгоритмам: задача Иосифа Флавия