Создание квантового источника света для фотонных чипов 
4 апреля (22 марта ст.ст.) 1905 г. — решение Синода о восстановлении 
Крот и ежик? 
У забора 
Разногласия по вопросу ЭКО: Франция расширяет доступ, США ограничивает 
Воспоминания про "Святые девяностые" 
Заявленные МО РФ потери артиллерии противника с 1 по 7 апреля 2024 года 
Риэлтор, который берет 25% от сделки... 
011022 полет к Вилючинскому вулкану, горнолыжный курорт Три вулкана ч2. Где я? Проект, над которым я работал в Твери последние 4 месяца завершен. 4 последних дня я провел в Саратове. В голове, конечно, была какая-то мысль, чтобы там остаться. Но провести в этом городе больше времени так и не смог. Это ужасно. Даже после Твери, которую многие (особенно ...
Сколько места требуется разряженной таблице
itman — 01.11.2010
Предположим, что есть таблица <�целый уникальный ключ,
значение>, отсортированная по ключу. Сколько требуется памяти
для этой таблицы (минус пространство занятое для записи значений)?
Целое влезает с в компьютерное слово.Понятно, что для самой таблицы достаточно <�размер ключа> * <�число записей>, но хочется, чтобы значение записи с заданным ключом можно было извлекать за O(1) операций доступа. Возможны также варианты хранения в trie-дереве (также неправильно известном, как radix-tree), или с помощью хеша. Но это дает overhead в O(<�размер указателя> * <�число элементов>). Можно ли сделать компактнее?
Комментарии скрывать не буду, это не вопрос для собеседования.
Оставить комментарий
Популярные посты:
Архив записей в блогах:
За длинные праздники мы так устали от тяжелых , не очень полезных блюд и сложных салатов! Некоторые, особо впечатлительные, при слове «майонез» меняются в лице… Теперь нам хочется еды простой и здоровой, но при этом все-таки вкусной . Мы припасли для вас несколько рецептов ...
"Я выстрадал свое решение, Оно пришло, как скорбный плач. Простит Господь мне прегрешенье - Казнен преступник и палач. Когда рассказ шел потрясающий О царской смерти, словно гром, Пред ликом ...
вот тока успела возненавидеть ЖЖистов- надомников,рассуждающих о внешней политике, как пора уже надомников-экономистов ненавидеть... б-дский хамон!!!! да чтоб вы так усердно трудились на благо семьи и Отечества, как кропаете свои умозаключения-нытьё.(велит)Всем- галоперидолу и спать!!!До ...
Называем один населённый пункт, город. Кто угадает ближе к которому упадёт Прогресс - тот победил и молодесс. А если серьёзно - ещё несколько миллионов и главное - символика... Две ракеты за две недели - это уже печально.... Наверно пора менять в консе что-то..... ...
