Амортизационный анализ, дурацкий вопрос
От: Sharov Россия  
Дата: 21.02.22 14:26
Оценка:
Здравствуйте.

Ну вот есть пример с динмаическим массивом -- тут
Т.е. у нас почти все операции за O(1), за исключением редких операций, когда массив надо удвоить
и скопировать эл-ты в новый массив, т.е. O(n). Но математика в конкретном случае такая, что несмотря на
эти тяжелые операции, все равно в среднем O(1).

Вопрос: а есть ли какие-нибудь обще употребимые структуры данных, где у нас доступ всегда O(1), кроме
редких случаев, когда надо что-то перестроить и т.п. вещи, и делается все это за, например, O(n^2)?
Соотв. у нас получится доступ, например, грубо, O(logn), только потому, что дорогие операции
"перераспределили" сложность на простые. Т.е. формально у нас O(1), но анализ говорит, что в среднем
это O(logn). Может какие индексы (а-ля как в бд), т.е. быстрый доступ, но дорого перестраивать? Или тензоры
и проч. многомерные массивы?
Кодом людям нужно помогать!
 
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.