0

目标：函数，它接受一个指向字符串的指针和两个长度，并在由长度表示的内部字符串之间进行交换，而不使用取决于输入大小的额外内存。例如，给定字符串“abcdef123”和长度 6,3，结果应该是“123abcdef”。

一种可能的递归实现（我的）是：

void invertStrings(char* str, int len1, int len2){
    if(len1==0 || len2==0)
        return;
    if(len1>len2){
        for(int i=0;i<len2;++i)
            swapChars(str, len1+i, len1-len2+i);
        invertStrings(str,len1-len2,len2);
    }
    else{
        for(int i=0;i<len1;++i)
            swapChars(str, len1+i, i);
        invertStrings(str+len1,len1,len2-len1);
    }
}

我认为时间复杂度是 O(len1+len2) 甚至可能是 O(max{len1,len2})。

问题：时间复杂度是多少，如何证明？谢谢。

4

2 回答 2

3

所写的算法似乎是O(len1+len2)。让我们将函数调用的“总工作量”定义为len1 + len2. 每次调用该函数时，它都会进行min(len1,len2)交换，并使用 递归调用自身total_work[n+1] = total_work[n] - min(len1,len2)。因此，所有递归调用中所做工作的上限是len1+len2.

这里的另一个转折是终止条件取决于gcd(len1,len2). 当 len1,len2 之一为 0 时循环终止，因此我们保证交换次数严格小于len1+len2. 最后“剩余”多少取决于两个长度的gcd。例如，如果我们(6,3)以 为起点，那么我们将得到(6,3)->(3,3)->(0,3), 总共 6 次掉期（少于预期的 8 次）。但如果我们从头开始，(7,3)->(4,3)->(1,3)->(1,2)->(1,1)->(1,0)我们最终会进行 9 次交换。掉期的数量一般正好是len1 + len2 - gcd(len1,len2).

于 2012-12-31T15:49:49.080 回答
0

这是O(n)，因为每个交换操作都会将至少一个字符放在正确的最终位置。

算法复杂度是输入大小的函数，这里操作的成本随着输入的大小线性增长。

通常具有复杂性，您只关心它表现出的增长类型。如果它是线性的，那么您不关心系数是多少（例如，您不关心它是输入数据量的两倍还是 7）。

于 2012-12-31T15:12:42.393 回答