Comments 35
Предлагаю посмотреть на проблему переполнений в арифметике под другим углом - чтобы переполнений не было, результат должен быть на 1 бит длиннее операндов. А значит, что первое, что второе решение на самом деле используют N/8 = O(N) байт дополнительной памяти.
То есть все эти трюки просто прячут дополнительную память среди неиспользуемых бит хранимых данных.
А может быть тут все гораздо проще, если мы говорим об амортизированном времени О(1)?
Тогда просто храним одну дополнительную переменную с максимальным числом в стеке. При добавлении значения в стек - сравниваем и при необходимости обновляем. При вынимании из стека это число будет меняться только если оно равно вершине стека. В таком случае при вынимании делаем обычный линейный поиск по стеку, чтобы найти предыдущее максимальное. Если я правильно понимаю, так для всех операций амортизированная сложность останется O(1)
Если я правильно понимаю, так для всех операций амортизированная сложность останется O(1)
Что случится с этим подходом, если числа вставлять последовательно? Нам придётся делать поиск максимума на каждой операции pop(), это O(n). В таком случае опустошение стека было бы O(n^2) - это очень плохо.
Второе возражение - О большое означает "худший случай", а не "средний случай".
Второе возражение - О большое означает "худший случай", а не "средний случай".
А вот и нет. Асимптотику можно определить для любой функции (и к тому же в любой точке, хоть обычно и смотрят на бесконечности), совершенно не обязательно чтобы эта функция означала худший случай.
Вычислительная сложность, насколько мне известно, рассматривается для больших значений n, я использую общепринятый подход и ничего своего не выдумываю.
Амортизированная сложность, если мне не изменяет память, обозначается Θ, а не O. Но если я ошибся, то давайте разбираться. O - это понятие, взятое из математики, ни о какой амортизиции там не должно идти речи.
Где вы это всё вычитали? Больше не читайте там ничего! Нет, Тета (Θ) не обозначает амортизированную сложность.
"O большое", "o малое", "Ω большая", "ω малая" и "Θ" - это асимптотические отношения-операторы, которые применимы к любой функции. Они все взяты из математики, более точно - из матанализа.
Амортизированная сложность - это функция. Любой математический инструмент, применимый к функциям, применим и к амортизированной сложности.
Да, O - это из мат анализа. T(n) = O(n) означает, что существует n0 и C > 0 такие, что для всех n > n0 выполнено T(n) < C * n, то есть "на любом входе нам достаточно не более чем линейного количества шагов".
Сложность алгоритма T(n) определяется как максимальное число шагов, требуемое для завершения алгоритма на входе размера n. Это общепринятый подход в теории алгоритмов.
Где вы это всё вычитали? Больше не читайте там ничего!
Мне книги по математике не читать больше? Видимо в них меня обманывают :)
Если я перепутал значение символа "тета", то скажите, что она на самом деле означает, и вопрос будет закрыт, я признаю ошибку. Но утверждать или намекать что я O большое неверно использовал - сильное заявление конечно. Вынужден попросить ссылку на пруф.
f(n) = Θ(g(n)) означает, что существуют n0, a и b > 0 такие, что для всех n > n0 выполнено 
Сложность алгоритма T(n) определяется как максимальное число шагов, требуемое для завершения алгоритма на входе размера n. Это общепринятый подход в теории алгоритмов.
Это лишь одна из возможных метрик алгоритма, но O-нотация применима к любой метрике.
Спасибо, эту часть прояснили, поспорить не смогу) Я так и писал:
Но если я ошибся, то давайте разбираться
Это лишь одна из возможных метрик алгоритма
Повествование именно о ней. Когда человек говорит "оценка временной сложности алгоритма", он имеет ввиду O(худшее время) либо Θ(худшее время), но не Θ(среднее время)
Асимптотику можно определить для любой функции
Кажется я разобрался, что вы хотели сказать. Мы по разному интерпретируем понятие "сложность алгоритма". Для меня это "число шагов в худшем случае, в зависимости от длины входа". Для вас это "среднее число шагов при каком-то заданном распределении входных данных длины n".
Согласно теории алгоритмов, "сложность" без дополнительных эпитетов - это именно что худшая сложность, а не средняя сложность.
Увы, но нет. Представьте следующую последовательность действий:
PUSH 100
PUSH 1 (N раз)
PUSH 100, POP (M раз)
Легко видеть, что ваш алгоритм сделает M линейных поисков по стеку. Если бы все операции амортизировались в O(1) - то общее время было бы O(1)*(N+2M+1)=O(N+M), а оно Θ(MN).
Ну, собственно для почти любого алгоритма можно придумать ситуацию когда он будет отрабатывать хуже чем «в среднем». Иначе бы не было такого зоопарка разнообразных алгоритмов сортировки.
Но я согласен, что наверное такая словесная эквилибристика и предложенное наивное решение - не то, что ожидает гугл в качестве решения подобной задачи. С другой стороны - путешествие в область переполнения интов, мне кажется, тоже излишне скользкий путь для задачки с собеседования.
Тут должно быть что то не совсем наивное но все таки достаточно детерминированное.
Вы сделали сильное и однозначное утверждение:
для всех операций амортизированная сложность останется O(1)
Для опровержения подобных утверждений достаточно одного-единственного контрпримера.
В контексте собеседования как раз важно, как заданы ограничения на входные данные, даже если это подразумевает путешествие в область переполнения интов. В этом и весь смысл, одна маленькая деталь в условиях делает правильные решения неправильными, и наоборот.
нужно реализовать стек, хранящий целые числа, в котором дополнительно должна существовать операция
max(), возвращающая максимальный элемент заO(1)времени и с использованиемO(1)дополнительной памяти (в сравнении со стеком без этой операции)
В условии задачи используется два три абстракции, реализация которые в реальных вычислительных системах сталкивается с ограничениями:
1. Стек. Классическое определение стека не имеет ограничений по емкости. В реальных системах емкость стека ограничена.
2. Целое число. В математике, целое число не имеет ограничений по разрядности. В реальных системах либо подразумевается ограничение по разрядности, либо число занимает переменное количество бит (или байт), и разрядность ограничена размером памяти, а размер стека дополнительно зависит от значения чисел в стеке.
3. Операция сравнения двух целых чисел. В реальных системах занимает О(1) времени только при условии, что разрядность целого числа ограничена. Для целых чисел с переменным количеством бит время выполнения операции сравнения зависит от собственно значения числа.
Если подразумевается, что программа реализуется на абстрактной машине, не имеющей указанных ограничений, то оба алгоритма являются верными. Но не в реальной реализации. Собственно, об этом и статья.
Если в задаче не задаются должным образом ограничения на входные значения, то это очень плохо, ведь буквально от этого зависит то, какие алгоритмы применимы для решения, а какие неприменимы.
Только почему у вас вместо стека получился список? Это должен быть некоторый линейный кусок памяти. Ну и раз max необходимо делать за константу, то единственный выход - сделать пересчёт максимума в push/pop. Причём достаточно хранить оффсет по стеку и делать дорогой пересчёт только в случае если стек уменьшили ниже этого значения. В остальных случаях пересчёт будет тоже близкий к константе.
Ограничений на время push/pop вам не выставляли, поэтому решение вполне себе простое и понятное.
Только почему у вас вместо стека получился список?
Прошу прощения, что вы имеете ввиду? Классический стек реализуется как раз как набор узлов, ссылающихся друг на друга, именно это гарантирует возможность вставки и удаления за O(1).
единственный выход - сделать пересчёт максимума в push/pop
Как было сказано в статье, перерассчёт - это не O(1).
Ограничений на время push/pop вам не выставляли
Видимо нужно было упомянуть, что они должны работать за O(1), думал что это само собой разумеющееся.
Прошу прощения, что вы имеете ввиду? Классический стек реализуется как раз как набор узлов, ссылающихся друг на друга, именно это гарантирует возможность вставки и удаления за O(1)
Не знаю как вы определяете "классичность", но обычно стеки всё-таки делают над массивами переменной длины - это даёт лучшую локальность обращений к памяти при той же амортизированной сложности.
Классический стек реализуется как раз как набор узлов
Вы явно с чем-то путаете. Классический стек - это кусок линейной памяти который при добавлении элемента "растёт" в сторону нуля. Большинство языков высокого уровня имеют структуру с именем Vector/Array которые предоставляют абстракцию над линейной памятью с константным доступом к элементу по индексу. Оно же является классическим стеком, предоставляя API для вставки/удаления элемента в конец этого контейнера за амортизированное константное время. Ноды появляются только в ситуации, когда вы делаете очередь или очередь с приоритетом, что как бы определённо не ваш кейс.
Как было сказано в статье, перерассчёт - это не
O(1).
А я и не утверждал, что оно будет константным. Оно будет деградировать до O(n) только при удалении текущего максимального элемента.
Видимо нужно было упомянуть, что они должны работать за
O(1)
Это не само собой разумеющееся в случае если вы делаете что-то нестандартное. И нет, полностью константный стек в действительно невозможен. Обычно если в задаче не пишут сложность для прочих методов, подразумевается, что их сложность не ограничена.
А я и не утверждал, что оно будет константным. Оно будет деградировать до O(n) только при удалении текущего максимального элемента.
А надо-то чтобы не деградировало
Если честно, я удивлён, что под стеком подразумевают вектор. Стек - это когда у тебя есть push и pop. По умолчанию я считаю, что они работают за O(1), именно так вводится "классическая" реализация стека из информатики.
И нет, полностью константный стек в действительно невозможен.
Уточните пожалуйста, что мы имеете ввиду. Стек, построенный на узлах со ссылками друг на друга не за истинно константное время добавляет/удаляет элементы?
EDIT: естественно я полагаю, что время аллокации, освобождения памяти и чтения/записи - константные. Кажется это тоже всегда неявно предполагается.
Ну, вообще-то да. Реальная динамическая память не обязательно за O(1) выделяется...
вставка в хвоста односвязного списка происходит за константу, да. Доступ к неголовному элементу у вас деградирует до O(n), но я так понимаю вы это не рассматриваете. Пересчёт максимального элемента аналогично - либо пересчёт max будет неконстантной, либо память. Соотвественно pop у вас автоматически деградирует до O(n)
Доступ к неголовному элементу у вас деградирует до O(n), но я так понимаю вы это не рассматриваете
У стека по определению есть доступ только к голове, в противном случае это уже не совсем стек.
либо пересчёт max будет неконстантной, либо память
Это совершенно неочевидный вывод, про который я и хотел поговорить подробнее в данной статье.
У стека по определению есть доступ только к голове, в противном случае это уже не совсем стек.
Только ваш стек умеет в max что хотя бы изнутри делает возможным произвольный доступ при наличии прочих типичных операций хотя бы внутри себя. И доступ соответственно будет происходить за линейное время из-за обхода списка.
Я не понимаю ваш аргумент. Если нужен внутри доступ к конкретному элементу стека, храните ссылку на него, а не порядковый номер. Это же ничего не изменит. И статья вообще не про это. Если использовать вектор, то всё равно не добиться решения с O(1) дополнительной памяти и O(1) дополнительного времени.
Чтобы не забыть, оставлю комментарий. Думаю попробовать сделать алгоритм без +/-, вместо них попробовать xor...
Стек с поиском максимума