Как оптимизировать стоимость конкатенации n строк

Если нам дано n строк и их длины, а также функция добавления (строка s1, строка s2), которая объединит строку s2 с s1 и вернет s3. Как бы мы оптимизировали стоимость конкатенации всех этих строк в одну большую строку.

Если бы такая функция не была задана, мы могли бы просто создать выходную строку размера (n1 + n2 + ...nn) и продолжать добавлять к ней символы каждой строки. Но с этой заданной функцией нам пришлось бы пройти входную строку s1, чтобы найти ее конец, а затем начать конкатенацию строки s2 с ней.

поэтому, если длина строк равна 2, 6, 1, 3, 4 ..

add (s1, s2) traversal for length 2, op string of length 8
add (s1, s3) traversal for length (2+6) op string of length 9
add (s1, s4) traversal for length (2+6+1) op string of length 12
add (s1, s5) traversal for length (2+6+1+3) op string of length 16...and so on..

optimization algorithm string-concatenation complexity-theory
person user1071840    schedule 11.10.2012    source источник
comment
Можете ли вы дать более точное определение того, что вы считаете стоимостью add() операции?   -  person rici    schedule 11.10.2012
comment
Я привел пример, что здесь под стоимостью я подразумеваю, сколько раз мне нужно пройти всю строку, и размер обхода увеличивается с точки зрения размера входных строк.   -  person user1071840    schedule 11.10.2012

Ответы (2)


arrow_upward
1
arrow_downward 

"with this function given we'd have to traverse input string s1 
to find it's end and then start concatenating string s2 to it. "

Вы можете объединить строку символ за символом, когда вы ее проходите. После добавления небольшой строки к строке результата вы можете получить указатель, указывающий на конец строки результата. Поэтому при добавлении следующей небольшой строки используйте ее, чтобы вам не пришлось снова проходить весь путь до этой позиции.

person Tejas Patil    schedule 11.10.2012

arrow_upward
0
arrow_downward

Есть два способа сделать это.

  1. Отсортируйте массив, а затем продолжайте конкатенацию, это сведет к минимуму затраты.

    Временная сложность O(nlogn), где n — размер массива. (Скажем, вы использовали быструю сортировку) Space Complexity O(logn)

  2. Создайте минимальную кучу массива. Теперь удалите первые две минуты из кучи, добавьте их
    и снова добавьте в кучу, сколько это займет?

    Создание Min-Heap займет O (n). Удаление 1-й и 2-й минут займет O (n) + O (n), подождите, как? , замените root последним элементом и вызовите heapify , он занимает O (logn), так же как и удаление . Теперь мы должны сделать то же самое для
    оставшихся n-2 элементов, так что это займет всего O(n-2(logn)), что наихудшее, добавить два элемента, взять O(1) и вставить обратно и снова настроить кучу будет взять O(logn) В целом это будет порядка O(nlogn), и мы также можем увидеть, что в таком случае требуется больше вызовов и инструкций.

Общая проблема просто требует сортировки массива, и мы можем минимизировать стоимость конкатенации, но если нам нужно больше думать о выборе правильного алгоритма сортировки, если мы рассматриваем время и пространство

person pyshcoguy    schedule 05.09.2013
comment
На самом деле вопрос, заданный ОП, не ясен, и поэтому неясно, чего пытается достичь этот ответ. - person justhalf; 05.09.2013
comment
@justhalf, вопрос задан, чтобы минимизировать стоимость объединения двух строк, давайте возьмем пример 1,5,2 - это длины данной строки в массиве (несортированные, добавляются по порядку) 1 + 5 = 6 6 + 2 = 8 общая стоимость =14 Вы можете оптимизировать общую стоимость? Да, что если отсортировать этот массив, он будет 1 2 5, а затем добавить 1 + 2 = 3, а затем 3 + 5 = 8, поэтому общая стоимость будет 11, что составляет ‹ 14, поэтому сортировка является одним из способов достижения оптимизации. - person pyshcoguy; 14.09.2013