AE
разворот это n
Size: a a a
2021 January 29
GS
в плане?
Если у нас уже где-то хранится в памяти список, и мы можем получить любой элемент, то уже просрали O(n) памяти на его хранение.
Я понимал условие так, что мы получаем список извне, и в лучшем случае получаем константу элементов за раз.
Я понимал условие так, что мы получаем список извне, и в лучшем случае получаем константу элементов за раз.
AE
А, ну да, было бы странно, если бы он уже хранился, потому что тогда условие некорректное было бы
GS
А, ну да, было бы странно, если бы он уже хранился, потому что тогда условие некорректное было бы
Двумя указателями ты по чему хочешь ходить?
AE
По списку же
T
а все понял
GS
По списку же
Где этот список хранится? Откуда взялся?
GS
Если в памяти приложения, то проигрыш, он занимает O(n)
AE
Ну так блят, логично же, что в таких задачах O(n) это именно дополнительно используемое место, потому что ты не можешь работать со списком, который в нигде
AE
И O(n) это пространство, занимаемое твоим алгоритмом
GS
Ну так блят, логично же, что в таких задачах O(n) это именно дополнительно используемое место, потому что ты не можешь работать со списком, который в нигде
Ну, нет, не логично, в олимпиадном программировании ограничения на память - это всегда ограничения на память твоего приложения.
Например, список может приходить из stdin, ты можешь запрашивать следующее число 10**6 раз, но хранить не можешь.
Например, список может приходить из stdin, ты можешь запрашивать следующее число 10**6 раз, но хранить не можешь.
z
И O(n) это пространство, занимаемое твоим алгоритмом
Не пространство а количество операций да ?
GS
Ну так блят, логично же, что в таких задачах O(n) это именно дополнительно используемое место, потому что ты не можешь работать со списком, который в нигде
Если список уже хранится в памяти, то не понятно, в чём хоть какая-то сложность задачи
AE
Не пространство а количество операций да ?
тут именно пространство
GS
Если список уже хранится в памяти, то не понятно, в чём хоть какая-то сложность задачи
берёшь и смотришь, готово
z
тут именно пространство
Чево
AE
Не могу отвечать сразу всем одновременно
GS
Не могу отвечать сразу всем одновременно
Юзай fifo
AE
берёшь и смотришь, готово
Как ты просто посмотришь в середину односвязного списка?
z
Не могу отвечать сразу всем одновременно
Превысили твои лимиты лол