AE
Остальные скучные
Size: a a a
2021 January 29
AE
O(1) от список плюс два указателя ? Или от чего ?
что
AE
Почитай че-нить классическое типа кормена
AE
Не шучу, правда, топ книжечка на полторы тысячи страниц
AE
Там в первых главах объясняют что такое асимптотика и как считать эффективность алгоритма
z
Я же тебя прямо спросил про твои понимания O(1) пространства а не что мне почитать
AE
@ShGKme не даст соврать, она правда топ
AE
Я же тебя прямо спросил про твои понимания O(1) пространства а не что мне почитать
Так мое понимание O(1) пространства то же, что и принято стандартом в изучении алгоритмов
GS
Давай, на собесах давать буду
Простая классика
На вход приходит N чисел.
Надо за O(n) времени и O(1) памяти понять, есть ли среди них повтор
На вход приходит N чисел.
Надо за O(n) времени и O(1) памяти понять, есть ли среди них повтор
AE
Твой алгоритм аллоцирует фиксированное количество памяти
GS
Есть по графам че-нить интересное?
Что такое интересное?
Как показывает практика, для тех, кто алгоритмические задачи не решает, хардовыми являются те же, что простые задачи для 8миклассников, которые их решают)
Как показывает практика, для тех, кто алгоритмические задачи не решает, хардовыми являются те же, что простые задачи для 8миклассников, которые их решают)
z
Ну так если ты константы откидываешь то 🤷🏻♂️ пространство будет O(2 * 1)
GS
Ну так если ты константы откидываешь то 🤷🏻♂️ пространство будет O(2 * 1)
O(2 * 1) = O(1) :)
GS
Тут даже алгоритмы не при чём, понятия О большое идёт из математики и формально определено
T
зерк учи матчасть…
AE
Ну так если ты константы откидываешь то 🤷🏻♂️ пространство будет O(2 * 1)
z
зерк учи матчасть…
Я как то по Уралу взял третье место на icpc, помолчи 😛
AE
Простая классика
На вход приходит N чисел.
Надо за O(n) времени и O(1) памяти понять, есть ли среди них повтор
На вход приходит N чисел.
Надо за O(n) времени и O(1) памяти понять, есть ли среди них повтор
Мы про массив?
AE
Типа если про массив, то изи, раньше давал такое
AE
Если про граф (я там просто про графы писал потом), то не понял задачу