Блог пользователя 175iq

Автор 175iq, история, 4 года назад, По-английски

I recently found out that inserting a vector in a map is possible :

map< vector<int>, int > mp;
vector<int> vec = {1,2,3,4,5};
mp[vec] = 5;
cout<<mp[vec];
// prints 5
  1. If there are N vectors in mp present as keys already, what is the time complexity to insert a new vector of size M in mp ? Is it O(M*log(N) or something else depending upon the sizes of vectors present in mp already?
  2. What would be the time complexity of a query operation such as mp[vec]? Please help.
  • Проголосовать: нравится
  • +21
  • Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится +12 Проголосовать: не нравится

Both are $$$O(M*lg(N))$$$

»
4 года назад, # |
Rev. 2   Проголосовать: нравится +46 Проголосовать: не нравится

Any type which has operator< defined can be inserted in the map. vector has this operator defined, that's why vector can be inserted in the map.

map is implemented as a self-balancing tree (usually red-black tree). Time taken in inserting or searching a key in self-balancing trees is O(log(N) * T(operator<)). For the case of vector time required for operator< is linear in terms of the size of the vector as this operator will require to traverse all the elements of the vector. Hence it will be O(log(N) * M).

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can I ask a similar question ?

if N is the size of vector

Is adding a map to vector having the complexity of O(N)

And if I sort a vector, is the complexity O(N log N)

  • »
    »
    4 года назад, # ^ |
    Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

    Yes.

    map < int , vector < int > > insertion has complexity O(log(map_size)+vector_size).

    sort(vec.begin(),vec.end()) has complexity O(vector_size*log(vector_size)*complexity_of_comparing).

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      What is the worst case of comparing ? I mean is it affect much ?

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        It depends on the vector's content. For example, vector < int > has complexity_of_comparing=O(1).

        • »
          »
          »
          »
          »
          4 года назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          oh, ok.

          And can I ask something more. If we want to use something to store sorted adj vertex. What is the best to use, vector<set> or vector<map<int, bool>>

»
4 года назад, # |
Rev. 3   Проголосовать: нравится +8 Проголосовать: не нравится

Well, strictly speaking, the complexity of calling mp[ver] or insert(vector,int) can be as high as log(N)*max_vector_length_in_mp, as c++ standard only guarantees O(log(N)) times of comparing, while not specifying which elements will be compared.

This is also related to how the compiler implements < between vectors. If comparing A and B costs O(|A|+|B|) instead of O(min(|A|,|B|))(as we would normally implement it), complexity can reach log(N)*max_vector_length_in_mp as well.

However, the two scenarios mentioned above are not so likely, so I guess for most compilers that complexity will be O(M*log(N)). Don't rely on that too much though, as priority_queue in GCC has already turned out to have used a rather strange(and counter-instinct) implemention, which makes the complexity of inserting a vector into it become log(N)*max_vector_length_in_mp.

  • »
    »
    4 года назад, # ^ |
    Rev. 5   Проголосовать: нравится 0 Проголосовать: не нравится

    Follow-up: another thing that I was interested in at some point is why std::sort of a vector of std::string elements would be linearithmic in the total size of the strings. I struggled to come up with a guarantee of any sort.

    Moreover, I couldn't figure out any algorithm that would sort a list of $$$N$$$ strings in the given complexity that would be easier than shuffling the $$$N$$$ strings and then inserting them into a BST one string at a time.

    In particular, I'm not sure how a regular binary max-heap would guarantee (even amortized) $$$O(\text{sum_of_lengths }log(N))$$$ for $$$N$$$ operations.

    Even harder follow-up: In some harder string problems, the solution is to sort strings with the comparator defined by the relationship $$$a \prec b \Leftrightarrow a + b < b + a$$$. This comparator has $$$O(|a| + |b|)$$$ complexity instead of $$$O(min(|a|, |b|))$$$. Why is it fast enough to std::sort using this comparator. Moreover, which sort algorithm would guarantee linearithmic complexity with this comparator?

    Any thoughts on these?

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      On sorting of strings, I think quicksort can handle the job in O(sum(length) log n) in expectation, even if comparing of strings A and B costs O(|A|+|B|). Mergesort can give the same complexity (without randomness) if comparing costs O(min(|A|,|B|)).

      On the complexity of binary heap (under the assumption that comparing is O(min(|A|,|B|))), let's consider two cases: 1. pop: After each comparing, one of the operands will take a step up in the heap, and let's count the cost in the element who goes up. 2. push: Similarly, with each comparing one operand goes up. The only exception is the last comparing. We count all these costs in the inserted element.

      It's not hard to prove that each element can only be counted O(log) times.

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        On the $$$|A| + |B|$$$ problem, even though it might go well in expectation, quicksort on strings can act quadratically with a probability of $$$1/n$$$, which is a lot higher than the "normal" quick-sort, and it is probably unwanted. For example, this might be problematic if you have one long string and (not too many) short strings.