c - 交换2个连续的字符串-时间复杂度

目标：函数，它接受一个指向字符串和两个长度的指针，并在由这些长度表示的内部字符串之间进行交换，而不使用依赖于输入大小的额外内存。
例如，给定字符串“abcdef123”和长度6,3，结果应为“123abcdef”。
一种可能的递归实现（mine）是：

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（Le1+LeN2），或者甚至可能是O（max {LeN1，LeN2}）。
问：时间复杂性是什么？它如何被证明？
谢谢。

最佳答案

编写的算法似乎是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)。