LeetCode 3304题C#解法的时间与空间复杂度分析问询

题目规则 #

初始字符串word为"a"，给定正整数k，每次操作将word中每个字符转为字母表下一个字符（'z'转为'a'），生成新字符串并追加到原word后，重复操作直到word长度≥k，返回第k个字符。

C# 解法代码 #

public char KthCharacter(int k) {
    string word = "a";
    int min = 97, max = 122;
    int letter = 0;

    int i = 0;

    while (word.Length < k)
    {
        string tempStr = "";
   
        while (i < word.Length)
        {
            letter = word[i++];
            letter++;
            if (letter > max) letter = min;
            char temp = Convert.ToChar(letter);
            tempStr +=  new string(new char[] {temp});
        }
        
        word += tempStr;
        i=0;
    }

    return word[k-1];
}

问题 #

该解法的时间复杂度（大O表示）是多少？我认为外层循环为O(logk)，因为word长度每次翻倍直至≥k；内层循环遍历当前word，长度逐次翻倍，为O(k)，总时间复杂度是否为O(k logk)？空间复杂度是否为O(k)？

复杂度分析 #

• 时间复杂度：确实是O(k logk)。外层循环次数为log₂k级别（因为每次word长度翻倍，从1增长到≥k需要约log₂k次循环）。每次外层循环中，内层循环要遍历当前word的所有字符：第一次遍历1个字符，第二次2个，第三次4个……直到总长度接近k。把这些遍历的字符数求和：1+2+4+…+2^m（其中2m < k ≤2^{(m+1)），总和为2}(m+1)-1，约等于2k，再乘以循环次数logk，整体时间复杂度就是O(k logk)。另外代码中tempStr的字符串拼接操作，由于C#字符串不可变，每次拼接都会生成新字符串，这部分开销也包含在O(k logk)的复杂度内。

• 空间复杂度：是O(k)。最终word的长度是≥k的最小2的幂（若k本身是2的幂则等于k），空间占用与k呈线性关系，因此空间复杂度为O(k)。

内容的提问来源于stack exchange，提问作者Ricardo