What is the time complexity of sorting a vector of vector

13 месяцев назад, # |

-8

If I were to bet, given the quite strict TL, I’m not sure I agree with aymanrs ‘s hypothesis.

I’ve never seen a counter-test where passing vectors by value would degenerate complexity (I conjecture that it’s $$$O(\log n)$$$ comparisons per element, yielding correct complexity). Can someone indicate one such test or a strategy to build it and prove me I’m blatantly wrong?

However, I do think that the reason why passing by value is slow here and passing by reference is not is memory allocation (one allocates a linear amount of memory, the other allocates linearithmic memory). This adds a condiderate constant factor to the solution.

→ Ответить

oversolver

13 месяцев назад, # ^ |

one big vector + many small?

→ Ответить

13 месяцев назад, # ^ |

← Rev. 3 →

Still, you would need to build a test case where the big vector gets compared with $$$\omega(\log n)$$$ elements, which is non-trivial as far as I'm aware (without digging into the intrinsics of how the std::sort algorithm works).

→ Ответить

13 месяцев назад, # ^ |

-37

if you will use merge sort, complexity will be O((sum len)* log(n)). It's because every element used in comparator O(log(n)) times.

But std::sort using quick sort algorithm. It's pick element and put lower element at begin and bigger element at end. Then recursive sort. So, if we will pick long vector it will be compared O(len(curr arr)) size.

→ Ответить

13 месяцев назад, # ^ |

-29

you may use stable_sort: [sorry, can't add link, because my submissions are hidden in this contest, but you can try it by yourself]

it's working in O(n log^2 n), but only O (log^2 n) comparisons for every element. So total will be O((sum len) * log^2 n)

→ Ответить

https://github.com/gcc-mirror/gcc/blob/d9375e490072d1aae73a93949aa158fcd2a27018/libstdc%2B%2B-v3/include/bits/stl_algo.h#L1950

13 месяцев назад, # ^ |

-26

hmm, ok, my words are true until C++11

since C++11 it's using other one algotihm:

is using aditional function

https://gcc.gnu.org/onlinedocs/libstdc++/libstdc++-html-USERS-4.4/a00978.html#7db47762a47726a861b61ecddd91e12e

It's using not a random element, but median of first, middle and last element and then split by this element.

So, in this case, first element is a median what will be found in first execution. You can random_shuffle array and get AC too. [also can't give a link for submission, but you also can check it by yourself. Add random_shuffle(a.begin(), a.end()); before sort]

→ Ответить

13 месяцев назад, # ^ |

-40

So, I think it's a good hack: std::random_shuffle array before sorting to minimize chance of picking big element by separator.

But also it's a good hack: using references in your functions)

→ Ответить

13 месяцев назад, # ^ |

-31

also, if you have a question: why std::sort using such type of sorting instead of merge sort?

It's all because of additional memory. If you want to sort elements in-place, you have to use in-place merging. It's not really hard algorithm of merging in O(n log (n)), but if you want to do it in O(n) — good luck, have fun. It's a really hard algorithm with big constant. you can read this article: https://www.google.com/url?sa=t&rct=j&q=&esrc=s&source=web&cd=&ved=2ahUKEwi3gd-o_Oz9AhVXyYsKHffiDW4QFnoECCQQAQ&url=https%3A%2F%2Fnms.kcl.ac.uk%2Finformatics%2Ftechreports%2Fpapers%2FTR-04-05.pdf&usg=AOvVaw3SELuk7H9SIx22TdHTn9ft

→ Ответить

13 месяцев назад, # ^ |

-31

Also you can use make_heap and sort_heap for sorting in place. It’s also unstable, and working O(n log n), but in real life some slower when sort.

→ Ответить

Sheyer

13 месяцев назад, # ^ |

+48

I think you should have edited the first comment instead of continuing to reply to it.

→ Ответить

daria.roganova71

13 месяцев назад, # ^ |

+27

I have some misunderstanding…

Why did you downvote this thread? It's a lot of interesting things about C++ standards, compilers, algorithms, and features of competitive programming.

Only because of a lot of messages? Lol?

What difference for you: read one big message or some small ones?

If you have questions, or you didn't agree – you can write it here…

You're just downvoting an interesting thread and what all.

Maybe because it's too hard for your Specialist brain? LMAO.

I hope you will be Expert one day…

→ Ответить

4qqqq

13 месяцев назад, # ^ |

+24

Sometimes I cant understand codeforces's users, tbh

→ Ответить

tezk

13 месяцев назад, # ^ |

As @oversolver said, the test case that got me TLE has 1 big vector and many small one. I have verified that it really is the sorting that kill my solution

→ Ответить

13 месяцев назад, # ^ |

+11

I never said otherwise. I was debating whether it's because the complexity becomes quadratic or the constant factor is too big.

→ Ответить

oversolver

13 месяцев назад, # ^ |

+13

just tested some cases and seems like std::sort make no more than log comparisons per item.

and talking about auto vs auto& in comparator generally, I have lot of experience even with pair<int,int> where reference gives major performance

→ Ответить

RozaliyaOlenyeva

13 месяцев назад, # ^ |

← Rev. 9 →

+27

When n is sufficiently large, sorting an ordered array causes the second element to be compared $$$\Theta(n)$$$ times. (However, I am still don't know how to construct it so that it reaches the complexity of $$$\Theta(n^2\log n)$$$)

Code

#include<bits/stdc++.h>
using namespace std;
int a[10001];
int cmp(int x,int y) {
   a[x]++;a[y]++;
   return x<y;
}
signed main() {
   vector<int> Q;
   for(int i=1;i<=10000;++i)
      Q.push_back(i);
   sort(Q.begin(),Q.end(),cmp);
   for(int i=1;i<=10000;++i)
      cerr << a[i] << ' ';
}

If you do random_shuffle first and then sort, then the complexity is also correct. But I don't think there is a sorting algorithm that can do $$$O(\log n)$$$ comparisons with worst-case luck.

upd: here's a sorting algorithm named "Bitonic Sort" can do $$$\Theta(\log n)$$$ comparisons for each element with worst-case luck.

→ Ответить

13 месяцев назад, # ^ |

← Rev. 3 →

+26

Let's keep things simple and assume std::sort is a merge sort algorithm. For the merge sort algorithm conjecture that it's $$$O(logN)$$$ comparison per element is blatantly wrong. It has a total $$$O(N*logN)$$$ comparison, but nowhere guaranteed that it's $$$O(logN)$$$ comparisons per element. Here is one such trivial counter-test case.

Spoiler

I do not want to dig into the intrinsics of how the std::sort algorithm works. What I know is std::stable_sort is implemented using merge sort. Here is a working example

→ Ответить

13 месяцев назад, # ^ |

JFYI: you can merge two arrays with O(log(n)) comparison for every element.

then you have two arrays A and B just do binary search how many element you have to use from A until first B element. It will be work in O(log(ans)), ans then you will move this elements in O(ans), so total is O(ans).

To do it you can firstly check all powers of two until first negative result and then search between $$$2^i$$$ and $$$2^{i+1}$$$

Total will be O(n)

→ Ответить

13 месяцев назад, # ^ |

← Rev. 2 →

+16

I never claimed all algorithms have $$$O(N)$$$ for an element. I just claimed native textbook code for merge sort can take $$$O(N)$$$ per element.
Also, can you elaborate more on your analysis?
Either I do not understand your algorithm, or it's $$$O(log^2N)$$$ comparisons per element, with the overall complexity being $$$O(N*log^2N)$$$

Merge sort has $$$O(logN)$$$ layers, and if we use your algorithm as an immediate step, it will take $$$O(log 2^i)$$$ comparisons on $$$i$$$ step, totalling $$$log^2(N)$$$ per element.

→ Ответить

13 месяцев назад, # ^ |

I told about merge component only. In merge sort — yes, it will be $$$O(log^2(N))$$$ comparisons per element.

→ Ответить

13 месяцев назад, # ^ |

Yes, that's indeed true. But for randomized quick sort on the other hand, the number of comparisons seems to be $$$O(\log n)$$$ per element on average.

Proof: An element $$$i$$$ will be compared to any other element:

when $$$i$$$ is a pivot (expected number of comparisons is $$$\sum{P(\text{sequence has }l\text{ elements}) \cdot l \cdot 1/l}$$$ = $$$1$$$)
when $$$i$$$ is compared to a pivot (expected number of comparisons is equal to expected depth, which is $$$O(\log n)$$$).

As far as I'm aware, std::sort is more like quick-sort than merge-sort, so I thought maybe it behaves similarly.

→ Ответить

https://codeforces.com/blog/entry/114167?#comment-1014962

13 месяцев назад, # ^ |

← Rev. 2 →

about std::sort — I wrote a thread under your previous comment. It downvoted a lot (Lol), but you can open comments.

→ Ответить

13 месяцев назад, # ^ |

← Rev. 5 →

If I'm the problem setter, here is one way I will try to hack quick-sort solutions.
Here, $$$N$$$ is up to $$$200000$$$.

Let's add $$$100$$$ vectors of length $$$1000$$$ each, rest $$$100000$$$ vectors with length $$$1$$$. For a particular test case, these large vectors get picked up as the first pivot with probability $$$0.001$$$. Add 100 such test cases, and the probability of avoiding TLE is $$$(1-0.001)^{100} = 0.904$$$; it's too risky when only one submission will be evaluated during system tests. It might work for educational rounds where people can make $$$10$$$ submissions. Parameters can be tweaked. Works well when sum is up to 2e6.

→ Ответить

dalex

13 месяцев назад, # ^ |

-8

And what's wrong with having a pivot of length 1000? Only 100 comparisons on each level of recursion will look through all these 1000 elements, other comparisons will stop at length 1.

→ Ответить