Временная сложность хеш-таблицы

Меня смущает временная сложность хеш-таблицы, во многих статьях утверждается, что они «амортизированы O (1)», а не истинным порядком O (1), что это означает в реальных приложениях. Какова средняя временная сложность операций в хеш-таблице, в реальной реализации, а не в теории, и почему операции не верны O (1)?

38
задан Daenyth 16 October 2010 в 14:46
поделиться