Сортировка строк.

Revision ru2, by maximumSHOT, 2016-03-18 17:47:33

Привет всем! Хотел узнать за сколько (асимптотика) работает сортировка строк следующим образом?

int n;
vector< string > a(n);
sort(a.begin(), a.end());

Будем считать, что все строки имеют длину от 1 до 1e5 и сумма длин всех строк не превышает 2e5. 1 <= sumLen <= 2e5

Количество строк от 1 до 1е5. 1 <= n <= 1e5

P.S. Известно, что существует сортировка строк за время O(sumLen) и O(sumLen * k) памяти или

за время O(sumLen * log(K)) и O(sumLen) памяти с помощью бора, но хотелось бы

разобраться с более короткой версией (с точки зрения написания кода). Заранее Спасибо!

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
ru2 Russian maximumSHOT 2016-03-18 17:47:33 5 Мелкая правка: '\nvector< int > a(n);\n' -> '\nvector< string > a(n);\n'
ru1 Russian maximumSHOT 2016-03-18 12:41:58 624 Первая редакция (опубликовано)