Зажать и присосаться: сравниваем эффективность механических и вакуумных захватов 
35 лет альбому Iron Maiden "No Prayer for the Dying" 
Встречи на прогулке 
Зачем мужику мышцы 
Гвардии рядовой Руслан Цепелев 
Осеннее сафари от Екатерининского парка до Воздвиженки 
Неожиданный Оруэлл. Размышления маленького человека накануне Второй Мировой: 
Выходные 
Мысли ПЗХ Платье из пунцового шёлка с серебряным шитьём. В этом платье Екатерина I была коронована Петром I в 1724 году. В настоящее время находится в коллекции Музеев Московского Кремля. ...
Сколько места требуется разряженной таблице
itman — 01.11.2010
Предположим, что есть таблица <�целый уникальный ключ,
значение>, отсортированная по ключу. Сколько требуется памяти
для этой таблицы (минус пространство занятое для записи значений)?
Целое влезает с в компьютерное слово.Понятно, что для самой таблицы достаточно <�размер ключа> * <�число записей>, но хочется, чтобы значение записи с заданным ключом можно было извлекать за O(1) операций доступа. Возможны также варианты хранения в trie-дереве (также неправильно известном, как radix-tree), или с помощью хеша. Но это дает overhead в O(<�размер указателя> * <�число элементов>). Можно ли сделать компактнее?
Комментарии скрывать не буду, это не вопрос для собеседования.
Оставить комментарий
Популярные посты:
Архив записей в блогах:
Я, видимо, всю жизнь буду бороться со своими суицидальными наклонностями, как другие борются с алкоголизмом или наркоманией. Эта зараза не отпускает навсегда. Сильнее всего меня эта страсть одолевала с 14 до 23 лет, потом с 37 до 45.Когда есть маленькие дети - то она отступает. Но едва ...
В прошлом году было очень много полезных разных проектов. Самый полезный, на мой взгляд (из тех, которые реально поменяли нашу жизнь к лучшему), - это «Московская поликлиника». Проект краудсорсинговый, или по-другому народный, участвовать в котором мог любой желающий. Суть в том, что люди ...
Ненавижу слово «потом». Неопределённое, подвешенное, раздражающее слово. Я его не понимаю. Оно ставит меня в тупик. Когда потом? Через час, через год, через жизнь? У меня нет времени ждать. Я живу сейчас. Это слово для ленивых душой чтобы ...
Онлайн-энциклопедия «Википедия» не была заблокирована на территории России, заявил ТАСС исполнительный директор «Викимедиа.ру», которая поддерживает русскоязычную версию энциклопедии, Станислав Козловский. По его словам, сообщений от пользователей из России, имеющих проблемы с доступом ...
