В декомпилированных исходниках Cyberpunk 2077, есть алгоритмы работающие со сложностью O(n^3). Потом люди удивляются, а чего игры лагают, даже на мощных ПК

3232

а теперь человеческим языком, не для безработных

39
Ответить

На обработку 3 единиц данных он затратит 27 действий.
На 27 единиц уже 19683 действия.
Ну ты понел.

25
Ответить

Сложность алгоритма кубически зависит от входных данных

6
Ответить

Там 3 while вложенных друг в друга.

Если просто - то пока самый последний while не выполнит все свои действия - первые 2 while будут ждать на своих 1 этапах. Потом начнется 2 этап и опять первые 2 while будут ждать и нихуя не делать.

Это пиздец.

4
Ответить

Я так понимаю речь о вложенных циклах while.

Цикл считается медленной операцией.
А тут их целых 3.
2 из которых еще и вложены в первый.

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

Если таких мест в коде много, а я думаю, что это не единственное место, то игра будет работать медленно.

Возможно код писался из-за сроков, быстро, поэтому делали все без оптимизации.

3
Ответить

Оценка сложности алгоритмов, проще всего понять опираясь вот на такой график.
При изменении значения n растет количество операций которые необходимо сделать при определенном количестве элементов на входе

Ответить