Есть ли место, где я могу получить анализ/сравнение стиля Big-O традиционных структур данных, таких как связанные списки, различные деревья, хэши и т. Д. как деревья Джуди и другие?Структуры и алгоритмы данных с высоким уровнем O и Cache Aware
Прочитано The Art of Computer Programming книги Дон Кнута. Многие считают, что они являются лучшим источником информации об алгоритме.
BigO примерно algorhitms сложность делая определенная задача. В каждой структуре данных существуют различные задачи. Наиболее важными являются: Сортировка, поиск (в отсортированной структуре) и добавление элемента.
Так что же вы ищете сложность определенной задачи для определенной структуры данных.
Для большинства типов данных полезна для оптимального сортировочных algorhitm О (п журнал (п)), но имейте в виду, что некоторые структуры еще медленнее, например, сортировки связанного списка медленнее, чем массивы Athough оба имеют п журнала (п) сложность
на самом деле,
Я хотел бы посмотреть here для анализа Judy деревьев.
Как показано в этих данных, меньшего размер Judy не дает ему преимущество в огромной скорости над традиционными «размером торговли для скорости» структур данных. Джуди получила бесчисленные человеко-часы разработки и отладка 20 000 строк кода; I потратил час или три на запись довольно стандартный 200-строчный хеш-стол.
Если ваши данные строго последовательны; вы должны использовать обычный массив. Если ваши данные часто являются последовательными или приблизительно последовательны (например, арифметическая последовательность , ступенчатая на 64), Возможно, Judy может быть лучшей структурой данных . Если вам нужно сохранить место до минимума - у вас есть огромное количество ассоциативных массивов , или вы только , хранящие очень маленькие значения, Judy , вероятно, хорошая идея. Если вам нужен отсортированный итератор , идите с Джуди. В противном случае хеш-таблица может быть такой же, как эффективна, возможно, быстрее, и многое другое проще.
ли вы смотреть в: «Введение в алгоритмы»
Спасибо, но я думал о чем-то немного более компактный ;-) –
Да ... это было немного язык в щеку меня ... – Oded
Muvan Me'alyv - Я не знаю, будет ли SO показывать иврит ... בא נראה –