Блин, пол третьего ночи. Пиздец.

алгоритм за квадрат

я не спорю

Потому что тебе надо внутри листа проходится.

но вставка константа

в хэш

Нет.

А мы тут сравнения неограниченных чисел смотрим.

да!

Других и не бывает.

У вас курсов по алгоритмама в узе не было?

да причём тут вуз

я сам алгоритмы изучал

При том что когда говорят про числа имеют в виду любы числа.

А не из набора.

мде

Если не огвоорено иное.

ты рассуждаешь как математик

а я как программист

Лол.

Смотрите. Чтение числа - logn, сравнение числе logn. Вставка числа в дерево logN. Чисел N. Значит сложность Nlogn*logN

с точки зрения 99% реальных задач, числа ограничены long long)

целые

Вот не надо тут про программист\математик. Я как раз таки программист

с точки зрения 99% реальных задач, числа ограничены long long)

Эм, нет.

нет, я мыслю как инженер

а ты как математик

Еще раз, с точки зрения «реальных задач» у тебя время работы всех алгоритмов константа.

инженера интересуют практические вещи, а тебя строгие и теоретические

Смотрите. Чтение числа - logn, сравнение числе logn. Вставка числа в дерево logN. Чисел N. Значит сложность Nlogn*logN

сравнение не за логарифм, все таки за константу.

в этом вся разница

Нет.

сравнение не за логарифм, все таки за константу.

Как ты за константу сравнишь числа?

Не надо за меня додумывать. Меня все вещи интересуют. Там был четкий вопрос в задаче.

Как ты за константу сравнишь числа?

целые?

да, ты как физик теоретик рассуждаешь о изотропии пространства и всяких таких вещах, а инженер тупо на глазок по приближенным формулам считает сопротивление балки

Как ты за константу сравнишь числа?

сравнил первый бит, если один больше то конец, если нет, то сравниваю второй, если один больше то конец, если одинаковые сравниваю третьий

целые?

Да, бесконечной длины.

сравнил первый бит, если один больше то конец, если нет, то сравниваю второй, если один больше то конец, если одинаковые сравниваю третьий

И это константа?

Да.

Да, бесконечной длины.

зависит от представления.

Да.

А мне кажется, что зависит от длины чисел.

Тебе неправильно кажется, могу объяснить почему.

как алгоритм называется сложения длинных чисел?)

забыл

Тебе неправильно кажется, могу объяснить почему.

Не откажусь.

там используется разложение на два члена

Потому что для двух произвольно взятых чисел совпадение первого бита вероятность — 1\2, совпадение первых двух 1\4, совпадение первых трёх 1\8

на две половины

Сумма ряда 1/2^n = 2

Сумма ряда 1/2^n = 2

1

слушайте, а зачем побитовое сравнение делать руками?

ну ты понял

есть же sse/avx и иже с ними

Лол.

слушайте, а зачем побитовое сравнение делать руками?

Здесь уже абстрактная хрень происходит. Не вмешивайся)

Мы говорим про модель вычислений.

Длинная арифметика обычная

Будет работать так.

Лол.

Кстати да. Если мы сконструируем СБИС, то всё будет делаться за константу)

Всё зависист от сложности схемы только)

Скорость света нам поможет)

создайте недетерминированную машину

Хотя нет, но со скоростью света на сложность пофиг)

и решайте np за полиномиальное время

Ладно, было интересно, но я спать. Спокойной ночи.

Здесь уже абстрактная хрень происходит. Не вмешивайся)

сферические кони в вакууме мало кому интересны. мне неинтересны габариты моей квартиры с точностью до микрон :)

ERROR: S client not available

сферические кони в вакууме мало кому интересны. мне неинтересны габариты моей квартиры с точностью до микрон :)

Ну, а нам интересны)

да, ты как физик теоретик рассуждаешь о изотропии пространства и всяких таких вещах, а инженер тупо на глазок по приближенным формулам считает сопротивление балки

В задаче требуется теоретическая оценка, чего ты еще-то хочешь? Я уже несколько раз обосновал почему любой способ разрешения коллизий для вставки работать будет за O(n)

сферические кони в вакууме мало кому интересны. мне неинтересны габариты моей квартиры с точностью до микрон :)

Это не сферические кони в вакууме

В задаче требуется теоретическая оценка, чего ты еще-то хочешь? Я уже несколько раз обосновал почему любой способ разрешения коллизий для вставки работать будет за O(n)

вставка будет за константу

Ох...

откуда ты взял требование проверки неодинаковости элементов в хеше?

Да ёпт. Начинается.

По определению.

по какому определению?

это если ты на основе хэша захотел set сделать

Меня мало волнует как в выдуманной твоей структуре что-то работает или в суперхештаблице андрея.

Вы говорите хеш-таблица.

хэш может хранить одинаковые ключи

Под ней понимается четкая структура данных

С пре и пост реквизитами

Меня мало волнует как в выдуманной твоей структуре что-то работает или в суперхештаблице андрея.

Блин, это даже обидно было)

Их определение в любой книге пожалуйста.

окей, где в определении хэш таблицы требование несовпадения ключей?

Ну потому что серьёзно, ваш ответ равносилен такому: МЫ ПОСТРОИМ СТРУКТУРУ ДАННЫХ, КОТОРАЯ БУДЕТ ЗА O(1) РЕШАТЬ НАШУЙ ЗАДАЧУ И ЕЩЕ БОРЩ ВАРИТЬ. ТЕПЕРЬ РЕШЕНИЕ СТРОИТСЯ ТАК: ВЫЗЫВАЕМ МЕТОД .ZDELAT_ZAEBIS У НАШЕЙ ВЫДУМАННОЙ СТРУКТУРЫ ДАННЫХ, ОН РАБОТАЕТ ЗА O(1) ПО НАШЕМУ ОПРЕДЛЕНИЮ. ХЗАДАЧА РЕШЕНА

нет такого требования

ты сам его придумал

вот если мы сет хотим создать на основе ХТ, тогда я согласен

слушайте, ну что мешает сделать двойное хеширование?

Определение хеш-таблицы это map key to value

map это по-русски отображение

нет

Отображение в математике имеет проообразом элемнта только один элемент.

Парни, вы спорите о разных вещах. Давайте не будем подрываться?

весело тут у вас.

Я вообще спора не вижу никакого. Просто говорю, что то, что предлагает Алдар — не хеш-таблица.

весело тут у вас.

Хотя бы хаскеля нет.