Несколько раз мне попадалась задача из разряда «собеседование в Google»:
нужно реализовать стек, хранящий целые числа, в котором дополнительно должна существовать операция max(), возвращающая максимальный элемент за O(1) времени и с использованием O(1) дополнительной памяти (в сравнении со стеком без этой операции).
Предполагаю, что многие тоже о ней слышали, а может даже знакомы с каким-либо решением. Про решения я и предлагаю поговорить, там всё очень интересно.
Подробная формулировка
Чтобы точно не возникало вопросов, предлагаю сперва зафиксировать требуемые сигнатуры. Я буду использовать язык Java, но всё должно быть понятно даже если вы с ним не знакомы.
// Обычные методы стека.
void push(int value);
int pop();
// Дополнительный метод.
int max();Решения с O(n)
Разберёмся с решениями задачи, которые используют ослабленные условия.
Если нам разрешено тратить
O(n)времени, то поиск максимума можно реализовать банальным поиском в стеке. Скучно и неинтересно.Если нам разрешено тратить
O(n)памяти, ноO(1)времени, то в качестве реализации можно использовать стек пар вида{value, max}— текущий элемент стека и текущий максимум стека. Или вообще сделать два стека, если совсем лень думать. Потребление памяти в таком подходе линейное. Тоже скучно и неинтересно.
Как решают задачу люди из интернета
Мне встречалось 2 решения. Они по своей сути эквивалентны, но на всякий случай приведу оба.
Решение 1
Воспользуемся тем фактом, что максимум всегда больше либо равен текущего элемента в стеке. То есть если отнять текущий элемент от текущего максимума, мы всегда получим число >= 0. Это даёт нам весь диапазон отрицательных чисел для кодирования чего-нибудь полезного, в случае если текущий элемент — максимальный. Например, мы можем закодировать предыдущий максимум.
Рассмотрим пример того, как в стек будут добавляться элементы:
stack := null
push 10:
// На дне стека всегда 0.
stack := {10 - 10 = 0} -> null
max := 10
push 7:
// 7 меньше максимума, поэтому значение в стеке положительное.
stack := {10 - 7 = 3} -> {10 - 10 = 0} -> null
max := 10
push 18:
// 18 больше максимума, поэтому значение в стеке отрицательное.
stack := {10 - 18 = -8} -> {10 - 7 = 3} -> {10 - 10 = 0} -> null
max := 18Обратная операция удаления из стека осуществляется похожим образом:
stack = {10 - 18 = -8} -> {10 - 7 = 3} -> {10 - 10 = 0} -> null
max = 18
pop, -8 < 0:
result := max = 18
max := max + -8 = 10 // Вычислили предыдущий максимум.
stack := {10 - 7 = 3} -> {10 - 10 = 0} -> null
pop, 3 >= 0:
result := max - 3 = 10 - 3 = 7
max := max = 10 // Не меняется.
stack := {10 - 10 = 0} -> null
pop, 0 >= 0:
result := max - 0 = 10 - 0 = 10
max := max = 10 // Не меняется, но это не важно, стек пустой.
stack := nullКод решения 1:
Скрытый текст
public class MaxStack1 {
static class Node {
final int value;
final Node next;
Node(int value, Node next) {
this.value = value;
this.next = next;
}
}
private Node top;
private int max;
public void push(int value) {
if (top == null) {
top = new Node(0, null); // max - value == 0
max = value;
} else {
top = new Node(max - value, top);
max = Math.max(value, max);
}
}
public int pop() {
if (top == null) {
throw new NoSuchElementException("Stack is empty");
}
Node oldTop = top;
top = oldTop.next;
if (oldTop.value >= 0) {
return max - oldTop.value;
} else {
int res = max;
max = max + oldTop.value;
return res;
}
}
public int max() {
if (top == null) {
throw new NoSuchElementException("Stack is empty");
}
return max;
}
}Решение 2
Оно уже более громоздкое, и построено на том же принципе — текущий элемент не может быть больше максимума. Но тут мы не будем вычислять разницу между value и max и сравнивать её с 0, мы сразу будем сравнивать value и max.
Если текущий элемент не максимальный, просто кладём его на вершину стека. Если же текущий элемент максимальный, то на вершину стека нужно положить какое-то значение, которое будет больше вставляемого value (которое станет новым max), по которому мы могли бы восстановить предыдущий максимум. Предлагается использовать следующую формулу:
value := 2 * value - max = value + (value - max)
max := valueЗдесь, конечно, делается небольшой финт ушами, который требует комментария:
Первое, что нужно заметить — это что
value - max > 0. Помним, чтоvalueв этом контексте — это новый максимум.Второе, что нужно заметить — это что
value + (value - max) > value, то есть значение на вершине стека будет больше хранимого впоследствии значенияmax. Ровно то, чего хотели достичь.
Рассмотрим пример на тех же числах, что и раньше:
stack := null
push 10:
// Тут нет предыдущего максимума, поэтому вставка
// в пустой стек выглядит особым образом.
stack := {10} -> null
max := 10
push 7:
// 7 меньше максимума.
stack := {7} -> {10} -> null
max := 10
push 18:
// 18 больше максимума.
stack := {2 * 18 - 10 = 26} -> {7} -> {10} -> null
max := 18Доставать элементы будем так:
stack = {2 * 18 - 10 = 26} -> {7} -> {10} -> null
max = 18
pop, 26 > 18:
result := max = 18
max := 2 * max - 26 = 2 * 18 - 26 = 10 // Тут просто обратная формула.
stack := {7} -> {10} -> null
pop, 7 <= 10:
result := 7
max := max = 10 // Не меняется.
stack := {10} -> null
pop, 10 <= 10:
result := 10
max := max = 10 // Не меняется, но это не важно, стек пустой.
stack := nullДанный подход, если судить по примеру, проще первого, вот только формула может вызвать больше вопросов, поэтому я и описал его вторым. Код решения 2:
Скрытый текст
public class MaxStack2 {
static class Node {
final int value;
final Node next;
Node(int value, Node next) {
this.value = value;
this.next = next;
}
}
private Node top;
private int max;
public void push(int value) {
if (top == null) {
top = new Node(value, null);
max = value;
} else if (value <= max) {
top = new Node(value, top);
} else { // value > max
top = new Node(2 * value - max, top);
max = value;
}
}
public int pop() {
if (top == null) {
throw new NoSuchElementException("Stack is empty");
}
Node oldTop = top;
top = oldTop.next;
if (oldTop.value <= max) {
return oldTop.value;
} else {
int res = max;
max = 2 * max - oldTop.value;
return res;
}
}
public int max() {
if (top == null) {
throw new NoSuchElementException("Stack is empty");
}
return max;
}
}Что не так с этими решениями?
Да вроде всё хорошо, если как на литкоде, брать -107 <= x <= 107. А если взять любой int, без читерских ограничений, которые обычно никем и не упоминаются?
Самое время рассказать, о чём эта статья на самом деле. Оба этих решения содержат очень похожие ошибки, которые я сейчас объясню.
Решение 1
Первое решение строилось на том свойстве, что если a >= b, то a - b >= 0. И наоборот, если a <= b, то a - b <= 0. А это, естественно, неправда!
Поскольку код я приводил на Java, мне проще считать, что все используемые числа — знаковые. С беззнаковыми типами нужно обращаться аккуратнее, но и на них можно было бы перенести все сделанные мною выводы.
Чтобы показать неверность указанного свойства, достаточно вспомнить про то, что числа "в компьютере" могут переполняться, и внезапно превращаться из положительных в отрицательные при, казалось бы, увеличении. Рассмотрим следующий пример:
a == Integer.MAX_VALUE, или же 231-1b == -1a > b, очевидноa - b == Integer.MAX_VALUE + 1 == Integer.MIN_VALUE < 0
Если взять числа, достаточно далеко расположенные друг от друга, то их разница может оказаться больше либо равной 231 и переполнить целочисленный диапазон. А это сломает инварианты, необходимые для правильного восстановления значения в коде pop. При использовании -107 <= x <= 107 такого переполнения, конечно же, случиться не может.
В общем случае это решение — неверное.
Решение 2
Уже вооружившись нужным инструментом, показать ошибочность решения 2 будет ещё проще. В нём мы, помимо свойства из решения 1, полагались на то, что если b > 0,
то a + b > a. То есть совершили ту же самую ошибку дважды.
Контрпример будет почти идентичный:
a == Integer.MAX_VALUEb == 1b > 0, очевидноa + b == Integer.MAX_VALUE + 1 == Integer.MIN_VALUE < a
Оно и понятно, всё же решения 1 и 2 мало отличаются что по подходу, что по требуемым предпосылкам. Итого оказывается, что нельзя просто так снять ограничения на входные данные и не упомянуть этого.
Почему?
Причина допущенной ошибки проста — авторы решений отождествляли свойства классической целочисленной арифметики и свойства 32-разрядной двоичной целочисленной арифметики. Делать этого ни в коем случае нельзя. Страшно даже представить, сколько из-за подобного мышления было совершено реальных ошибок в реальных проектах.
Казалось бы, в интернете кто-то не прав, и что с того? Если спросить меня об этом, то я скажу примерно следующее: одно дело, когда ты читаешь политические срачи в комментариях, и совершенно другое дело, когда ты читаешь образовательные материалы от людей, которые должны тебя чему-то учить. Авторы подобных образовательных материалов не выполнили свою работу должным образом и ввели читателей в заблуждение, это плохо.
Я спокойно могу себе представить собеседование в условный «Яндекс», на котором собеседующий мог бы дать эту конкретную задачу с неверными граничными условиями и буквально ожидать от собеседуемого неправильного решения. Ведь давайте будем честны — часто ли мы настолько внимательно проверяем то, что прочитали в интернете, или скопировали из ответа на StackOverflow, к примеру? Нам тоже стоит помнить, что ответы в интернете пишут люди, которые могут ошибаться, даже если у ответа много плюсиков.
Но это я отвлёкся.
Как тогда выглядит правильное решение?
Вероятнее всего, никак. Мой тезис таков — при условиях O(1) времени и O(1) дополнительной памяти задача вообще не имеет решения.
Формального доказательства не будет, вместо этого будет обзор определённого класса решений и некоторое количество рассуждений. Возможно я в них ошибаюсь, это уже уйдёт на суд читателя.
Что общего между решениями 1 и 2, если посмотреть на них совсем абстрактно? То, что в дополнение к стеку с целыми числами они вводят ровно одну дополнительную целочисленную переменную. Я попробую обосновать, почему это — совершенно бесперспективный подход, для этого понадобится вспомнить немного информатики.
Чтобы было совсем наглядно, предлагаю работать не с 32-битными числами, а с 2-битными числами. Так же я буду их интерпретировать как беззнаковые числа, чтобы упросить понимание текста. Очевидно, что знаковость/беззнаковость интерпретации битов фундаментально ничего не меняет.
Если хранить максимум
Представим, что у нас есть 2-битное число на вершине стека (cur) и дополнительно хранимый 2-битный максимум (max). Хранение в дополнительной переменной какого-то значения, отличного от максимума, я прокомментирую позже. Суммарно это 4 бита информации.
Сколько информации нам нужно при выполнении операции pop? Рассмотрим все возможные варианты:
Максимум равен
0(минимальное допустимое значение), текущее значение обязано тоже быть равным0.-
Максимум равен
1.Текущее значение может быть равно
0или1, предыдущий максимум всё ещё равен1.Текущее значение равно
1(текущий максимум), предыдущий максимум равен0.
-
Максимум равен
2.Текущее значение может быть равно
0,1или2, предыдущий максимум всё ещё равен2.Текущее значение равно
2(текущий максимум), предыдущий максимум равен0или1.
-
Максимум равен
3.Текущее значение может быть равно
0,1,2или3, предыдущий максимум всё ещё равен3.Текущее значение равно
3(текущий максимум), предыдущий максимум равен0,1или2.
Итого, имеем (1) + (2 + 1) + (3 + 2) + (4 + 3) = 16 различных вариантов. Вплотную ровно для того, чтобы всё можно было уместить в 4 бита информации. Для больших разрядностей битов тоже будет хватать, причём также впритык.
Небольшая математическая выкладка для пояснения, приводится без доказательства:
В чём же проблема?
Проблема в том, как эта информация должна быть закодирована. Если переменная max хранит текущий максимальный элемент, то в случае, когда она равна 3 (максимальный из всех максимальных), мы оставшимися двумя битами должны покрыть 7 возможных исходов, а именно:
4 варианта текущего значения, если оно не максимально.
3 варианта значения предыдущего максимума.
Это просто невозможно сделать оставшимися двумя битами, и будет невозможно для всех разрядностей.
Что если кодировать данные иначе?
Представим, что у нас есть некое 2-битное значение на вершине стека (cur) и дополнительно хранимая 2-битная переменная (extra). Вместе они каким-либо способом образуют 4-х битное число, способное описать все требуемые нам 16 вариантов исхода. К примеру, мы просто пронумеровали все возможные исходы и поместили их в таблицу. Достаточно ли будет так поступить? Давайте думать.
Мы способны однозначно восстановить текущий элемент, текущий максимум и предыдущий максимум, используя данные нам 4 бита. Это уже хорошо. После того, как вершина стека будет удалена, нам требуется восстановить предыдущее состояние переменной extra, то есть какие-то 2 бита из выбранной нами нумерации.
Фактически, перед нами встала ровно та же проблема, что была при наличии переменной max вместо extra. Если выяснится то, что предыдущий максимум должен быть равен 3 (исходя из текущего состояния вершины стека), то после удаления текущей вершины стека у нас появится ровно 2 бита дополнительной информации (элемент в стеке), чтобы различить всё те же 7 вариантов, повторю их:
4 варианта текущего значения, если оно не максимально.
3 варианта значения предыдущего максимума.
Получается очень забавно. У нас достаточно бит информации, но в них тупо не хватает энтропии (так часто бывает в неверных решениях задач про рычажные весы и монетки). Судя по всему, иная кодировка данных не способна фундаментально ничего изменить. Без дополнительных бит в стеке у нас не хватает информации, а дополнительные биты — это уже O(n) дополнительной памяти.
Что если мы расширим количество бит в переменной extra? Лучше не станет. На вершине стека то всё ещё 2 бита, их не будет хватать.
Конечно, есть ненулевой шанс того, что и я всё напутал и пришёл к неверным выводам. Ошибаюсь, бывает. Но я правда не вижу здесь места для ошибки, так что всех несогласных приглашаю к диалогу в комментариях, вместе мы найдём истину.
Что в итоге
Если в задаче не задаются должным образом ограничения на входные значения, то это очень плохо, ведь буквально от этого зависит то, какие алгоритмы применимы для решения, а какие неприменимы. На том же литкоде ограничения пишут не просто так, и если ты видишь работу с массивами длиной в миллион, то скорее всего наивный алгоритм с O(n^2) не прокатит. Тут почти то же самое.
Люди в интернете, которые стараются вас чему-то научить, могут про такие ограничения забыть. Вряд-ли специально. Когда я впервые ознакомился с решением данной задачи про стек, оно как раз было преподнесено мне в виде «должно работать для всех значений int».
Так что будьте аккуратны с целыми числами и граничными условиями. Спасибо за внимание!
Комментарии (35)
lexus6666
18.09.2024 07:34А может быть тут все гораздо проще, если мы говорим об амортизированном времени О(1)?
Тогда просто храним одну дополнительную переменную с максимальным числом в стеке. При добавлении значения в стек - сравниваем и при необходимости обновляем. При вынимании из стека это число будет меняться только если оно равно вершине стека. В таком случае при вынимании делаем обычный линейный поиск по стеку, чтобы найти предыдущее максимальное. Если я правильно понимаю, так для всех операций амортизированная сложность останется O(1)
ibessonov Автор
18.09.2024 07:34Если я правильно понимаю, так для всех операций амортизированная сложность останется O(1)
Что случится с этим подходом, если числа вставлять последовательно? Нам придётся делать поиск максимума на каждой операции
pop(), этоO(n). В таком случае опустошение стека было быO(n^2)- это очень плохо.Второе возражение -
Обольшое означает "худший случай", а не "средний случай".
mayorovp
18.09.2024 07:34+1Второе возражение - О большое означает "худший случай", а не "средний случай".
А вот и нет. Асимптотику можно определить для любой функции (и к тому же в любой точке, хоть обычно и смотрят на бесконечности), совершенно не обязательно чтобы эта функция означала худший случай.
ibessonov Автор
18.09.2024 07:34Вычислительная сложность, насколько мне известно, рассматривается для больших значений
n, я использую общепринятый подход и ничего своего не выдумываю.Амортизированная сложность, если мне не изменяет память, обозначается
Θ, а неO. Но если я ошибся, то давайте разбираться.O- это понятие, взятое из математики, ни о какой амортизиции там не должно идти речи.mayorovp
18.09.2024 07:34Где вы это всё вычитали? Больше не читайте там ничего! Нет, Тета (Θ) не обозначает амортизированную сложность.
"O большое", "o малое", "Ω большая", "ω малая" и "Θ" - это асимптотические отношения-операторы, которые применимы к любой функции. Они все взяты из математики, более точно - из матанализа.
Амортизированная сложность - это функция. Любой математический инструмент, применимый к функциям, применим и к амортизированной сложности.
ibessonov Автор
18.09.2024 07:34Да,
O- это из мат анализа.T(n) = O(n)означает, что существуетn0иC > 0такие, что для всехn > n0выполненоT(n) < C * n, то есть "на любом входе нам достаточно не более чем линейного количества шагов".Сложность алгоритма
T(n)определяется как максимальное число шагов, требуемое для завершения алгоритма на входе размераn. Это общепринятый подход в теории алгоритмов.Где вы это всё вычитали? Больше не читайте там ничего!
Мне книги по математике не читать больше? Видимо в них меня обманывают :)
Если я перепутал значение символа "тета", то скажите, что она на самом деле означает, и вопрос будет закрыт, я признаю ошибку. Но утверждать или намекать что яOбольшое неверно использовал - сильное заявление конечно. Вынужден попросить ссылку на пруф.mayorovp
18.09.2024 07:34f(n) = Θ(g(n)) означает, что существуют n0, a и b > 0 такие, что для всех n > n0 выполнено
Сложность алгоритма T(n) определяется как максимальное число шагов, требуемое для завершения алгоритма на входе размера n. Это общепринятый подход в теории алгоритмов.
Это лишь одна из возможных метрик алгоритма, но O-нотация применима к любой метрике.
ibessonov Автор
18.09.2024 07:34Спасибо, эту часть прояснили, поспорить не смогу) Я так и писал:
Но если я ошибся, то давайте разбираться
ibessonov Автор
18.09.2024 07:34Это лишь одна из возможных метрик алгоритма
Повествование именно о ней. Когда человек говорит "оценка временной сложности алгоритма", он имеет ввиду
O(худшее время)либоΘ(худшее время), но неΘ(среднее время)
ibessonov Автор
18.09.2024 07:34Асимптотику можно определить для любой функции
Кажется я разобрался, что вы хотели сказать. Мы по разному интерпретируем понятие "сложность алгоритма". Для меня это "число шагов в худшем случае, в зависимости от длины входа". Для вас это "среднее число шагов при каком-то заданном распределении входных данных длины
n".Согласно теории алгоритмов, "сложность" без дополнительных эпитетов - это именно что худшая сложность, а не средняя сложность.
mayorovp
18.09.2024 07:34Не читайте в моих сообщениях того, чего я не писал. Лучше прочтите ещё раз своё:
Второе возражение - О большое означает "худший случай", а не "средний случай".
Так вот, нет, не означает.
ibessonov Автор
18.09.2024 07:34+1Да, мне нужно было подробнее высказываться.
Более полная фраза, которую я должен был написать - "когда говорят, что трудоёмкость алгоритма равна O от чего-то, то имеют ввиду худший случай". В этом смысле моя фраза оказалась неточной
mayorovp
18.09.2024 07:34+1Увы, но нет. Представьте следующую последовательность действий:
PUSH 100 PUSH 1 (N раз) PUSH 100, POP (M раз)Легко видеть, что ваш алгоритм сделает M линейных поисков по стеку. Если бы все операции амортизировались в O(1) - то общее время было бы O(1)*(N+2M+1)=O(N+M), а оно Θ(MN).
lexus6666
18.09.2024 07:34Ну, собственно для почти любого алгоритма можно придумать ситуацию когда он будет отрабатывать хуже чем «в среднем». Иначе бы не было такого зоопарка разнообразных алгоритмов сортировки.
Но я согласен, что наверное такая словесная эквилибристика и предложенное наивное решение - не то, что ожидает гугл в качестве решения подобной задачи. С другой стороны - путешествие в область переполнения интов, мне кажется, тоже излишне скользкий путь для задачки с собеседования.
Тут должно быть что то не совсем наивное но все таки достаточно детерминированное.
mayorovp
18.09.2024 07:34+1Вы сделали сильное и однозначное утверждение:
для всех операций амортизированная сложность останется O(1)
Для опровержения подобных утверждений достаточно одного-единственного контрпримера.
ibessonov Автор
18.09.2024 07:34В контексте собеседования как раз важно, как заданы ограничения на входные данные, даже если это подразумевает путешествие в область переполнения интов. В этом и весь смысл, одна маленькая деталь в условиях делает правильные решения неправильными, и наоборот.
Dotarev
18.09.2024 07:34нужно реализовать стек, хранящий целые числа, в котором дополнительно должна существовать операция
max(), возвращающая максимальный элемент заO(1)времени и с использованиемO(1)дополнительной памяти (в сравнении со стеком без этой операции)В условии задачи используется
дватри абстракции, реализация которые в реальных вычислительных системах сталкивается с ограничениями:
1. Стек. Классическое определение стека не имеет ограничений по емкости. В реальных системах емкость стека ограничена.
2. Целое число. В математике, целое число не имеет ограничений по разрядности. В реальных системах либо подразумевается ограничение по разрядности, либо число занимает переменное количество бит (или байт), и разрядность ограничена размером памяти, а размер стека дополнительно зависит от значения чисел в стеке.
3. Операция сравнения двух целых чисел. В реальных системах занимает О(1) времени только при условии, что разрядность целого числа ограничена. Для целых чисел с переменным количеством бит время выполнения операции сравнения зависит от собственно значения числа.Если подразумевается, что программа реализуется на абстрактной машине, не имеющей указанных ограничений, то оба алгоритма являются верными. Но не в реальной реализации. Собственно, об этом и статья.
Если в задаче не задаются должным образом ограничения на входные значения, то это очень плохо, ведь буквально от этого зависит то, какие алгоритмы применимы для решения, а какие неприменимы.
domix32
18.09.2024 07:34Только почему у вас вместо стека получился список? Это должен быть некоторый линейный кусок памяти. Ну и раз max необходимо делать за константу, то единственный выход - сделать пересчёт максимума в push/pop. Причём достаточно хранить оффсет по стеку и делать дорогой пересчёт только в случае если стек уменьшили ниже этого значения. В остальных случаях пересчёт будет тоже близкий к константе.
Ограничений на время push/pop вам не выставляли, поэтому решение вполне себе простое и понятное.
ibessonov Автор
18.09.2024 07:34Только почему у вас вместо стека получился список?
Прошу прощения, что вы имеете ввиду? Классический стек реализуется как раз как набор узлов, ссылающихся друг на друга, именно это гарантирует возможность вставки и удаления за
O(1).единственный выход - сделать пересчёт максимума в push/pop
Как было сказано в статье, перерассчёт - это не
O(1).Ограничений на время push/pop вам не выставляли
Видимо нужно было упомянуть, что они должны работать за
O(1), думал что это само собой разумеющееся.mayorovp
18.09.2024 07:34Прошу прощения, что вы имеете ввиду? Классический стек реализуется как раз как набор узлов, ссылающихся друг на друга, именно это гарантирует возможность вставки и удаления за O(1)
Не знаю как вы определяете "классичность", но обычно стеки всё-таки делают над массивами переменной длины - это даёт лучшую локальность обращений к памяти при той же амортизированной сложности.
ibessonov Автор
18.09.2024 07:34Не знаю как вы определяете "классичность"
Так, как это делается в учебной литературе. Стек, реализованный поверх массива - это уже разновиднось, реализуемая после, именно как альтернатива.
domix32
18.09.2024 07:34Классический стек реализуется как раз как набор узлов
Вы явно с чем-то путаете. Классический стек - это кусок линейной памяти который при добавлении элемента "растёт" в сторону нуля. Большинство языков высокого уровня имеют структуру с именем Vector/Array которые предоставляют абстракцию над линейной памятью с константным доступом к элементу по индексу. Оно же является классическим стеком, предоставляя API для вставки/удаления элемента в конец этого контейнера за амортизированное константное время. Ноды появляются только в ситуации, когда вы делаете очередь или очередь с приоритетом, что как бы определённо не ваш кейс.
Как было сказано в статье, перерассчёт - это не
O(1).А я и не утверждал, что оно будет константным. Оно будет деградировать до O(n) только при удалении текущего максимального элемента.
Видимо нужно было упомянуть, что они должны работать за
O(1)Это не само собой разумеющееся в случае если вы делаете что-то нестандартное. И нет, полностью константный стек в действительно невозможен. Обычно если в задаче не пишут сложность для прочих методов, подразумевается, что их сложность не ограничена.
mayorovp
18.09.2024 07:34А я и не утверждал, что оно будет константным. Оно будет деградировать до O(n) только при удалении текущего максимального элемента.
А надо-то чтобы не деградировало
domix32
18.09.2024 07:34Он не квантовым алгоритмом занимается, так что это принципиально невозможно. У обычного стека и без того вставка обычно амортизированная.
ibessonov Автор
18.09.2024 07:34+1Если честно, я удивлён, что под стеком подразумевают вектор. Стек - это когда у тебя есть
pushиpop. По умолчанию я считаю, что они работают заO(1), именно так вводится "классическая" реализация стека из информатики.И нет, полностью константный стек в действительно невозможен.
Уточните пожалуйста, что мы имеете ввиду. Стек, построенный на узлах со ссылками друг на друга не за истинно константное время добавляет/удаляет элементы?
EDIT: естественно я полагаю, что время аллокации, освобождения памяти и чтения/записи - константные. Кажется это тоже всегда неявно предполагается.
mayorovp
18.09.2024 07:34Ну, вообще-то да. Реальная динамическая память не обязательно за O(1) выделяется...
ibessonov Автор
18.09.2024 07:34Реальная динамическая память не обязательно за O(1) выделяется
Естественно, но нужно же где-то остановиться. А то получится, что ещё скорость диска нужно учитывать, на котором программа лежит)
domix32
18.09.2024 07:34вставка в хвоста односвязного списка происходит за константу, да. Доступ к неголовному элементу у вас деградирует до O(n), но я так понимаю вы это не рассматриваете. Пересчёт максимального элемента аналогично - либо пересчёт max будет неконстантной, либо память. Соотвественно pop у вас автоматически деградирует до O(n)
ibessonov Автор
18.09.2024 07:34+1Доступ к неголовному элементу у вас деградирует до O(n), но я так понимаю вы это не рассматриваете
У стека по определению есть доступ только к голове, в противном случае это уже не совсем стек.
либо пересчёт max будет неконстантной, либо память
Это совершенно неочевидный вывод, про который я и хотел поговорить подробнее в данной статье.
domix32
18.09.2024 07:34У стека по определению есть доступ только к голове, в противном случае это уже не совсем стек.
Только ваш стек умеет в max что хотя бы изнутри делает возможным произвольный доступ при наличии прочих типичных операций хотя бы внутри себя. И доступ соответственно будет происходить за линейное время из-за обхода списка.
ibessonov Автор
18.09.2024 07:34Я не понимаю ваш аргумент. Если нужен внутри доступ к конкретному элементу стека, храните ссылку на него, а не порядковый номер. Это же ничего не изменит. И статья вообще не про это. Если использовать вектор, то всё равно не добиться решения с
O(1)дополнительной памяти иO(1)дополнительного времени.
mayorovp
Предлагаю посмотреть на проблему переполнений в арифметике под другим углом - чтобы переполнений не было, результат должен быть на 1 бит длиннее операндов. А значит, что первое, что второе решение на самом деле используют N/8 = O(N) байт дополнительной памяти.
То есть все эти трюки просто прячут дополнительную память среди неиспользуемых бит хранимых данных.
ibessonov Автор
Всё так, они прячут дополнительную память, полностью согласен! Но делают это неявно, ведь там как было 32 бита, так и осталось