python - 试图理解连接字符串输出的空间复杂度

Question

我在编码面试中遇到了这个问题:

# AAABB should return A3B2

这是一道经典的算法面试题。我说过我可以在 O(n) 时间和 O(1) 空间内解决这个问题。

def compress(s):

    output = ''
    count = 1

    for i in range(len(s)-1):
        if s[i] == s[i+1]:
            count+=1
        else:
            output = output + s[i] + str(count)
            count=1

    output = output +s[i+1] + str(count)
    return output

compress('AAABB') #returns A3B2

我理解 O(n) 空间意味着它随着输入的大小按比例增长。所以我在想 O(n) 空间看起来像 [(A,3),(B,2)]。

我的印象是 A3B2 在 O(1) 空间中，因为它没有被拆分成多个字符串。

我现在意识到 n == len(s) 并且我的输出增长与我的输入大小不成比例(更少)，所以说空间是 O(登录 n)?

Answer 1

必须统计你存储的输出字符串的长度。在最坏的情况下(没有连续的字符匹配)，它实际上是输入的两倍长。很明显，一般来说它是 O(n):如果您以某种方式知道长输入总是包含非常长的运行，它只会渐进地更好。 (在最好的情况下，所有字符都相同，并且一个 number 的长度是 O(log n)。)

也就是说，有时将您的输出视为一个流(如 print)是很有用的，然后是您的空间复杂度(对于 count 和可能的当前输入字符)是常数。当然，即便如此，它在技术上也是对数的，因为存储 count 所需的位数是，但在实际分析中经常忽略这一点。