Если у меня есть arrs list<vector<int>> и temp vector<int> ,

Question

supapro.cxx

Andrey

Если у меня есть arrs list<vector<int>> и temp vector<int> ,

то arrs.insert(it, std::move(temp)) будет работать за O(1)? я правильно понял?

#c #embedded #programming #russian

0

11.11.2023

4 ответов

21 просмотр

Andrey Автор вопроса

Ilya Zviagin
Да

bool comp(const vector<int>& a, const vector<int>& b){ return a[a.size() - 1] > b[b.size() - 1]; } void shift_down(std::list<std::vector<int>>& arr){ // O(logK) vector<int> temp = std::move(*arr.begin()); // O(1) arr.pop_front(); // O(1) if(temp.empty()) return; auto it = std::upper_bound(arr.begin(), arr.end(), temp, comp); // O(logK) ?? arr.insert(it, std::move(temp)); // O(1) } а такая штука за O(logk), где k - arrs.size()?

0

6 месяцев назад

Ilya Zviagin

Andrey
bool comp(const vector<int>& a, const vector<int>&...

Тут много операций, какую надо оценивать?

0

6 месяцев назад

Ilya Zviagin

Andrey
bool comp(const vector<int>& a, const vector<int>&...

Ну вроде да, если я ничего не пропустил

0

6 месяцев назад