Сложность отсортированного списка Mongo

Для следующего отсортированного списка:

{
   sorted_list : [{name : <string>,score : <Number>}]
}

В чем сложность следующих команд (в обозначениях «О»)?

Находить:

collection.find( { _id: 1}, { sorted_list: { $slice: [ <skip>, <limit> ] } } )

Вставлять:

collection.update(
   { _id: 1 },
   {
     $push: {
       sorted_list: {
         $each: [ { name: 3, score: 8 }, { name: 4, score: 7 }, { name: 5, score: 6 } ],
         $sort: { score: 1 }
       }
     }
   }
)

Удалять:

collection.update({"sorted_list.name": name},{ $pull: { "sorted_list.name": <name> } },{ multi: true });

ИЗМЕНИТЬ

Предположим, что существует следующий индекс:

{ "sorted_list.name" : 1}


person skme    schedule 13.01.2015    source источник
comment
Здесь три операции. Поиск и удаление довольно просты, так как в одном используются записанные индексы, а в другом также может по-разному влиять проиндексированное содержимое (так же, как и обновление, если на то пошло). Если здесь есть вопрос, то, похоже, он больше касается обновления. Как в результате введения значений n в существующий список элементов x и выполнения сортировки. Вы понимаете, что растущие документы в MongoDB без выделенного места означают, что они физически перемещаются. Вероятно, это должно быть больше вашей заботы, чем отображение сложности.   -  person Neil Lunn    schedule 13.01.2015
comment
Итак, подводя итог: Найти - O(пропустить+лимит). Удалить (с учетом индекса) - O(n), где n - количество записей в списке. Обновление - пока остается вопросом. Насчет распределения места, наверное, вы правы, но это уже отдельный вопрос.   -  person skme    schedule 13.01.2015
comment
Это на самом деле более важный вопрос. Теория сложности на самом деле ничего не решит за вас, кроме домашних заданий. Но помимо того, что я указываю на то, что ваш вопрос состоит из трех вопросов, есть ... 1. Я упоминал значения массива с индексами? Да, я думаю. 2. Суть вопроса, но указал, что вы должны спросить. 3. Переменная по слишком многим факторам. Другие могут отличаться, но меня лично не впечатляют те, кто хочет доказать, что они только что закончили информатику или математику. Здесь важнее решать реальные проблемы.   -  person Neil Lunn    schedule 13.01.2015