1

n 個の文字列とその長さと、文字列 s2 を s1 と連結して s3 を返す add(string s1,string s2) 関数が与えられた場合。これらすべての文字列を 1 つの大きな文字列に連結するコストを最適化するにはどうすればよいでしょうか。

そのような関数が指定されていない場合、単純にサイズ (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..
4

2 に答える 2

1 
"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. "

文字列をトラバースするときに、文字列を文字ごとに連結できます。結果文字列に小さな文字列を追加すると、結果文字列の末尾を指しているポインターを取得できます。したがって、次の小さな文字列を追加するときは、それを使用して、その位置までもう一度トラバースする必要がないようにします。

于 2012-10-11T04:59:00.493 に答える
0

それを行うには 2 つの方法があります。

  1. 配列をソートして連結し続けると、コストが最小限に抑えられます。

    時間計算量 O(nlogn) n は配列のサイズです。(クイックソートを使用したとします) Space Complexity O(logn)

  2. 配列の最小ヒープを作成します。ヒープから最初の 2 分を削除し、それら
    を追加して再度ヒープに追加します。どのくらいかかりますか?

    Min-Heap の作成には O(n) かかります。1st Min と 2nd Min を削除すると O(n)+O(n) かかります。、ルートを最後の要素に置き換え、 heapify を呼び出します。O(logn) が必要なので、削除します。ここで、残りの n-2 要素に対して同じことを行う必要がある
    ため、合計 O(n-2(logn)) が必要になります。最悪の場合、2 つの要素を追加して O(1) を取得し、ヒープを再度挿入して調整すると O( logn) 全体的には O(nlogn) の順序になり、そのような場合により多くの呼び出しと命令が必要になることもわかります。

全体的な問題は、配列を並べ替えるだけで、連結のコストを最小限に抑えることができますが、時間と空間を考慮している場合、正しい並べ替えアルゴリズムの選択についてもっと考える必要がある場合

于 2013-09-05T07:26:59.053 に答える