Всё.

Алдар, какова сложность инсёрта в хештейбл7

Сложность функции + logn

У тебя n чисел

Значит O(n^2)

Нихуя не логарифм.

инсерт константный

лол

В хештаблицу в худшем случае вставка за O(n)

инсерт константный

Тогда поиск будет за O(n)

просто хэш память жрёт

инсерт константный

Ага, конечно. Книжки по алгоритмам давно открывал?

откуда линейная сложность?

Да ёб, вы что троллите?

считаем хэш, индекс у массива

и вставляем

в список по индексу

откуда тут линейной сложности появится?

Ага, конечно. Книжки по алгоритмам давно открывал?

Вообще да, константная сложность.

-_____-

окей, расскажи мне когда будет линейная сложность?

Марш учить алгоритмы!

когда будет рехеш

тут у нас рехеширования не будет

потому что мы знаем количество элементов заранее

вообще вставка в хэш это амортизированная константа

ЛОЛ

амортизированная потому, что иногда рехеш случается

Чувак, ты разницу между средним и худшим понимаешь?

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

при вставке

Чувак, ты разницу между средним и худшим понимаешь?

В твоём случае худший вариант - это вставка 1 элемента.

Да, и вставка одного элемента может занять в худшем случае O(n)

Да, и вставка одного элемента может занять в худшем случае O(n)

опиши мне худший случай

в квиксорте худший случай это когда массив уже отсортирован и мы пивот берём первый элемент

Худший случай: у всех элементов одинаковое значение хеш функции.

Да, и вставка одного элемента может занять в худшем случае O(n)

Ок. Алгоритм такой. У тебя есть хеш-функция, которая принимает значения 0..N. Тs выделяешь эту память за *контантное время*. Далее ты за константное время заполняешь хеш таблицу.

Ноуп.

Это не алгоритм.

У меня нет хеш-функции.

Худший случай: у всех элементов одинаковое значение хеш функции.

Так не надо тупо заполнять. Заполняй умно: проверяй при добавлении в хеш таблицу, заполнена ли она или нет.

Я заранее не знаю, что за элементы.

Что значит тупо?

Еще раз.

Ты вообще знаешь что такое хеш-таблица?

Ты вообще знаешь что такое хеш-таблица?

Нет, блять, я дибил. Решил поспорить перед сном.

Видимо, да. Хеш-таблица это просто штука, в которую можно класть элементы и проверять есть ли там такой элемент( про удаление даже не говорим сейчас).

Я тебе привёл алгоритм. Найди там сложность O(n^2)/

Вставляем в хеш без затрат времени ?

Какой алгоритм -__-

Вставляем в хеш без затрат времени ?

Этими затратами можно пренебречь.

Андрей, мне кажется ты не понимаешь что такое хэш таблица

Ок. Алгоритм такой. У тебя есть хеш-функция, которая принимает значения 0..N. Тs выделяешь эту память за *контантное время*. Далее ты за константное время заполняешь хеш таблицу.

Этими затратами можно пренебречь.

Вот в том-то и прикол что нельзя

Так не надо тупо заполнять. Заполняй умно: проверяй при добавлении в хеш таблицу, заполнена ли она или нет.

У меня НЕТ хеш функции.

Ты неявно полагаешь, что я откуда-то возьму хеш-функцию.

универсальной хеш-функции нет!!!!!!

хэш функция для натурального числа это id

Либо надо написать самому хеш, в который ты можешь вставлять бесплатно

допустим

теперь у тебя есть хэш функция

поэтому в данном случае мы можем считать что достаточно хорошая хэш функция у нас есть

Ладно, я не вижу смысла здесь спорить. Сначала тебя не устраивает алгоритм, а после ты переключаешься на отсутствие хеш-функции. Хреново с тобой спорить.

Хотя я насчёт алгоритма только говорил.

ERROR: S client not available

А ты на меня по поводу хеш-функции наезжаешь.

Почитай кормена, я серьёзно.Посмотри почему википедия со мной согласна.

Потому что это важно.

Если бы всё было так просто как ты говоришь, std::set бы работал в плюсах за o(1)

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

на всех операциях

Но он такне работает

Если бы всё было так просто как ты говоришь, std::set бы работал в плюсах за o(1)

Если у тебя бесконечная память, то будет работать за O(1)

Опять же нет.

Даже если хэш функция на все числа возвращает одно и тоже число - вставка в таблицу будет константа

Ноуп.

при условии что мы разрешает коллизии с помощью списка

Опять же нет.

Оппа, ок. У меня бесконечная память. На что мне тратить О(n)?

то есть имеем массив списков

потому что есть другой метод разрешения коллизий

это когда ты просто кладёшь в следующую свободную ячейку

Чуваки. Я серьёзно. Вот вы мне не верите. окей. Я могу сейчас расписать по пунктам в чем вы не правы, но чисто для себя вы можете объяснить, почему википедия со мной согласна?

потому что в википедии общий случай

Почему любая книжка по алгоритмам скажет вам, что хештейбл в худшем случае даёт n

а мы говорили про конкретную задачу и конкретную хэш функцию

Что значит, общий случай?

Про какую конкретную задачу?

Чуваки. Я серьёзно. Вот вы мне не верите. окей. Я могу сейчас расписать по пунктам в чем вы не правы, но чисто для себя вы можете объяснить, почему википедия со мной согласна?

Чувак, O(n) в худшем случае только из-за коллизий. Если у нас бесконечная память, то коллизий нет.

поиск пары одинаковых элементов в массиве

Чувак, O(n) в худшем случае только из-за коллизий. Если у нас бесконечная память, то коллизий нет.

Как тебя спасает бесконечная память?

Хеш-функцию ты как строишь?

Хеш-функция ПО ОПРЕДЕЛЕНИЮ имеет ОГРАНИЧЕННОЕ число значений.

Хеш-функция ПО ОПРЕДЕЛЕНИЮ имеет ОГРАНИЧЕННОЕ число значений.

Нет.

ещё раз, есть массив, там все элементы разные, кроме пары одинаковых

Дат.

ограниченное и счётное это разные вещи

функция id не является хеш-функцией.