Увидев заголовок статьи, я сразу подумал о тех программистах с 10 годами опыта, которых называют сениорами лишь из-за стажа, а реальные навыки у них как у мидлов. Но нет, совсем наоборот, тут о том, что где-то требуют 3 года опыта в вакансии. Это точно статья не про личную обиду? Ситуация, когда человек с 2 годами опыта настолько крут, что его можно брать на более старшую позицию, так невероятно редка, что я бы не стал её всерьёз рассматривать. Тем более, такой человек смог бы в частном порядке с работодателем договориться, просто показав своё портфолио. Ссылку на гитхаб, к примеру
Я не понимаю ваш аргумент. Если нужен внутри доступ к конкретному элементу стека, храните ссылку на него, а не порядковый номер. Это же ничего не изменит. И статья вообще не про это. Если использовать вектор, то всё равно не добиться решения с O(1) дополнительной памяти и O(1) дополнительного времени.
Если честно, я удивлён, что под стеком подразумевают вектор. Стек - это когда у тебя есть push и pop. По умолчанию я считаю, что они работают за O(1), именно так вводится "классическая" реализация стека из информатики.
И нет, полностью константный стек в действительно невозможен.
Уточните пожалуйста, что мы имеете ввиду. Стек, построенный на узлах со ссылками друг на друга не за истинно константное время добавляет/удаляет элементы?
EDIT: естественно я полагаю, что время аллокации, освобождения памяти и чтения/записи - константные. Кажется это тоже всегда неявно предполагается.
Только почему у вас вместо стека получился список?
Прошу прощения, что вы имеете ввиду? Классический стек реализуется как раз как набор узлов, ссылающихся друг на друга, именно это гарантирует возможность вставки и удаления за O(1).
единственный выход - сделать пересчёт максимума в push/pop
Как было сказано в статье, перерассчёт - это не O(1).
Ограничений на время push/pop вам не выставляли
Видимо нужно было упомянуть, что они должны работать за O(1), думал что это само собой разумеющееся.
Да, мне нужно было подробнее высказываться. Более полная фраза, которую я должен был написать - "когда говорят, что трудоёмкость алгоритма равна O от чего-то, то имеют ввиду худший случай". В этом смысле моя фраза оказалась неточной
Повествование именно о ней. Когда человек говорит "оценка временной сложности алгоритма", он имеет ввиду O(худшее время) либо Θ(худшее время), но не Θ(среднее время)
В контексте собеседования как раз важно, как заданы ограничения на входные данные, даже если это подразумевает путешествие в область переполнения интов. В этом и весь смысл, одна маленькая деталь в условиях делает правильные решения неправильными, и наоборот.
Кажется я разобрался, что вы хотели сказать. Мы по разному интерпретируем понятие "сложность алгоритма". Для меня это "число шагов в худшем случае, в зависимости от длины входа". Для вас это "среднее число шагов при каком-то заданном распределении входных данных длины n".
Согласно теории алгоритмов, "сложность" без дополнительных эпитетов - это именно что худшая сложность, а не средняя сложность.
Да, O - это из мат анализа. T(n) = O(n) означает, что существует n0 и C > 0 такие, что для всех n > n0 выполнено T(n) < C * n, то есть "на любом входе нам достаточно не более чем линейного количества шагов".
Сложность алгоритма T(n) определяется как максимальное число шагов, требуемое для завершения алгоритма на входе размера n. Это общепринятый подход в теории алгоритмов.
Где вы это всё вычитали? Больше не читайте там ничего!
Мне книги по математике не читать больше? Видимо в них меня обманывают :) Если я перепутал значение символа "тета", то скажите, что она на самом деле означает, и вопрос будет закрыт, я признаю ошибку. Но утверждать или намекать что я O большое неверно использовал - сильное заявление конечно. Вынужден попросить ссылку на пруф.
Вычислительная сложность, насколько мне известно, рассматривается для больших значений n, я использую общепринятый подход и ничего своего не выдумываю.
Амортизированная сложность, если мне не изменяет память, обозначается Θ, а не O. Но если я ошибся, то давайте разбираться. O - это понятие, взятое из математики, ни о какой амортизиции там не должно идти речи.
Если я правильно понимаю, так для всех операций амортизированная сложность останется O(1)
Что случится с этим подходом, если числа вставлять последовательно? Нам придётся делать поиск максимума на каждой операции pop(), это O(n). В таком случае опустошение стека было бы O(n^2) - это очень плохо.
Второе возражение - О большое означает "худший случай", а не "средний случай".
Обычно я задаю больше одного вопроса) Опыт собеседований, совсем слабых коллег у меня к счастью нет EDIT: думаю стоит всё же уточнить - нам в работе алгоритмы нужны, бесполезных задач на собеседованиях не даём, всё жизненное
Увидев заголовок статьи, я сразу подумал о тех программистах с 10 годами опыта, которых называют сениорами лишь из-за стажа, а реальные навыки у них как у мидлов.
Но нет, совсем наоборот, тут о том, что где-то требуют 3 года опыта в вакансии. Это точно статья не про личную обиду?
Ситуация, когда человек с 2 годами опыта настолько крут, что его можно брать на более старшую позицию, так невероятно редка, что я бы не стал её всерьёз рассматривать. Тем более, такой человек смог бы в частном порядке с работодателем договориться, просто показав своё портфолио. Ссылку на гитхаб, к примеру
Я не понимаю ваш аргумент. Если нужен внутри доступ к конкретному элементу стека, храните ссылку на него, а не порядковый номер. Это же ничего не изменит. И статья вообще не про это. Если использовать вектор, то всё равно не добиться решения с
O(1)дополнительной памяти иO(1)дополнительного времени.У стека по определению есть доступ только к голове, в противном случае это уже не совсем стек.
Это совершенно неочевидный вывод, про который я и хотел поговорить подробнее в данной статье.
Естественно, но нужно же где-то остановиться. А то получится, что ещё скорость диска нужно учитывать, на котором программа лежит)
Если честно, я удивлён, что под стеком подразумевают вектор. Стек - это когда у тебя есть
pushиpop. По умолчанию я считаю, что они работают заO(1), именно так вводится "классическая" реализация стека из информатики.Уточните пожалуйста, что мы имеете ввиду. Стек, построенный на узлах со ссылками друг на друга не за истинно константное время добавляет/удаляет элементы?
EDIT: естественно я полагаю, что время аллокации, освобождения памяти и чтения/записи - константные. Кажется это тоже всегда неявно предполагается.
Так, как это делается в учебной литературе. Стек, реализованный поверх массива - это уже разновиднось, реализуемая после, именно как альтернатива.
Прошу прощения, что вы имеете ввиду? Классический стек реализуется как раз как набор узлов, ссылающихся друг на друга, именно это гарантирует возможность вставки и удаления за
O(1).Как было сказано в статье, перерассчёт - это не
O(1).Видимо нужно было упомянуть, что они должны работать за
O(1), думал что это само собой разумеющееся.Да, мне нужно было подробнее высказываться.
Более полная фраза, которую я должен был написать - "когда говорят, что трудоёмкость алгоритма равна O от чего-то, то имеют ввиду худший случай". В этом смысле моя фраза оказалась неточной
Повествование именно о ней. Когда человек говорит "оценка временной сложности алгоритма", он имеет ввиду
O(худшее время)либоΘ(худшее время), но неΘ(среднее время)В контексте собеседования как раз важно, как заданы ограничения на входные данные, даже если это подразумевает путешествие в область переполнения интов. В этом и весь смысл, одна маленькая деталь в условиях делает правильные решения неправильными, и наоборот.
Спасибо, эту часть прояснили, поспорить не смогу) Я так и писал:
Кажется я разобрался, что вы хотели сказать. Мы по разному интерпретируем понятие "сложность алгоритма". Для меня это "число шагов в худшем случае, в зависимости от длины входа". Для вас это "среднее число шагов при каком-то заданном распределении входных данных длины
n".Согласно теории алгоритмов, "сложность" без дополнительных эпитетов - это именно что худшая сложность, а не средняя сложность.
Да,
O- это из мат анализа.T(n) = O(n)означает, что существуетn0иC > 0такие, что для всехn > n0выполненоT(n) < C * n, то есть "на любом входе нам достаточно не более чем линейного количества шагов".Сложность алгоритма
T(n)определяется как максимальное число шагов, требуемое для завершения алгоритма на входе размераn. Это общепринятый подход в теории алгоритмов.Мне книги по математике не читать больше? Видимо в них меня обманывают :)
Если я перепутал значение символа "тета", то скажите, что она на самом деле означает, и вопрос будет закрыт, я признаю ошибку. Но утверждать или намекать что я
Oбольшое неверно использовал - сильное заявление конечно. Вынужден попросить ссылку на пруф.Вычислительная сложность, насколько мне известно, рассматривается для больших значений
n, я использую общепринятый подход и ничего своего не выдумываю.Амортизированная сложность, если мне не изменяет память, обозначается
Θ, а неO. Но если я ошибся, то давайте разбираться.O- это понятие, взятое из математики, ни о какой амортизиции там не должно идти речи.Что случится с этим подходом, если числа вставлять последовательно? Нам придётся делать поиск максимума на каждой операции
pop(), этоO(n). В таком случае опустошение стека было быO(n^2)- это очень плохо.Второе возражение -
Обольшое означает "худший случай", а не "средний случай".Всё так, они прячут дополнительную память, полностью согласен! Но делают это неявно, ведь там как было 32 бита, так и осталось
Сижу теперь и думаю, как я это пропустил. Спасибо, я поправлю статью. Извиняюсь за косяк
Не понятно - уделите побольше времени прочтению. Понятия описаны, алгоритмы приведены, доказательства есть по ссылкам, код есть.
Если серьёзно, то что нужно добавить? Я в будущем учту. Просто то же самое, но подробнее?
Обычно я задаю больше одного вопроса) Опыт собеседований, совсем слабых коллег у меня к счастью нет
EDIT: думаю стоит всё же уточнить - нам в работе алгоритмы нужны, бесполезных задач на собеседованиях не даём, всё жизненное
Опыт собеседований показывает, что и с 5-летним опытом бывают совсем слабые, тут как повезёт