Estimating Time Complexity
What would be the time complexities of A -> 145542635 and B -> 145539763.
How to calculate time complexity when there are variable number of inserts, push_backs happening?
I don't know your algorithm but:
AC solution:
set<pair<int, int> > st; ... st.erase({degree[nbr], nbr}); degree[nbr]--; st.insert({degree[nbr], nbr});
set is red-black tree, so erase and insert both takes O(log|st|) time
set
erase
insert
O(log|st|)
TLE solution:
vector<int> graph[n+1]; ... graph[nbr].erase(find(graph[nbr].begin(), graph[nbr].end(), j));
vector just linear array, so find is just loop. It is O(|graph[nbr]|). erase is just shift all right-side elements + pop_back, it is too O(|graph[nbr]|)
vector
find
O(|graph[nbr]|)
pop_back
for(int i : to_be_removed) { for(int nbr : graph[i]) { if(st.find({degree[nbr], nbr}) != st.end()) { st.erase({degree[nbr], nbr}); degree[nbr]--; st.insert({degree[nbr], nbr}); } } }
Better rewrite to
for(int i : to_be_removed) { for(int nbr : graph[i]) { if(auto it = st.find({degree[nbr], nbr}); it != st.end()) { // start from C++ 17 st.erase(it); degree[nbr]--; st.insert({degree[nbr], nbr}); } } }
Difference that in first version there are two searches for {degree[nbr], nbr}. In second version it is single search.
{degree[nbr], nbr}
I don't know your algorithm but:
AC solution:
set
is red-black tree, soerase
andinsert
both takesO(log|st|)
timeTLE solution:
vector
just linear array, sofind
is just loop. It isO(|graph[nbr]|)
.erase
is just shift all right-side elements +pop_back
, it is tooO(|graph[nbr]|)
Better rewrite to
Difference that in first version there are two searches for
{degree[nbr], nbr}
. In second version it is single search.