试图理解连接字符串输出的 space 复杂性

Question

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

# AAABB should return A3B2

这是一道经典的算法面试题。我说我可以在 O(n) 时间和 O(1) space.

内解决这个问题

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) space的意思是随着输入的大小按比例增长。所以我在想 O(n) space 看起来像 [(A,3),(B,2)].

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

我现在意识到 n == len(s) 并且我的输出增长与我的输入大小不成比例（更少），所以说 space 是 O(log n) 是正确的吗？

Answer 1

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

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

试图理解连接字符串输出的 space 复杂性

Trying to understand the space complexity of concatenated string output

python

algorithm

time-complexity

asymptotic-complexity

space-complexity