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

Sorting A vector of strings

Автор _comfortably_numb, история, 6 лет назад, По-английски

Recently I faced few problems where I needed to use a map of strings or sort a vector of strings.

The number of strings can be upto 10^5, but the summation of lengths of the strings won't be larger than 10^5.

Now, I wonder what is the complexity of this sorting ? And can you please explain why ?

  • Проголосовать: нравится
  • +32
  • Проголосовать: не нравится

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

It's easier to analyze if you maintain a set (sorted) of the strings and insert them one by one. The length of the currently inserted string is L. Since we do comparisons with it and other already inserted strings, the complexity is worstcase , and so the total cost of inserting all strings is .

→ Ответить
»
6 лет назад, # |
  Проголосовать: нравится +34 Проголосовать: не нравится

The time complexity of comparing two strings s1 and s2 of length n1 and n2 is clearly, . So, the worst case input corresponds to input strings having equal length m. Assume the input consists of n strings. The length of each string ( in the case of all strings having equal length ) will be . The 105 comes into the picture to satisfy the constraints in your question. For the case of sorting, if there are n elements, the total number of comparisons is . Here, we also need to account for the comparison between two strings, which, in our case, is m. Multiplying we get, .

→ Ответить