这个解的时间复杂度是 O(logn) 吗？

Question

我已经为一个挑战编写了以下解决方案，但我不确定它的时间复杂度：def ASCIIConversion(string):     newStr = ''    for chr in string:        if chr.isspace():             newStr = newStr + ' '        else:            newStr += str(ord(chr))    return newStr程序的复杂度 O(logn) 是不是因为 else 语句？

Answer 1

最坏情况下的时间复杂度计算如下（假设字符串最大长度为 n）：

newStr = ''  # will be done once so 1 time.

for chr in string: # is iterating on the input with max length of n so n times.

    if chr.isspace(): # will be checked once it is in the loop so 1 time per each iteration.

        newStr = newStr + ' ' # also once per iteration if the if condition is satisfied

    else: # will be chehcked once per iteration

        newStr += str(ord(chr)) # if else is satisfied

return newStr # will be done 1 time.

我们将假设常数时间是 c 所以：

Time complexity = 1 + n(c*c + c*c) + 1 = 2+Cn => O(n)

Answer 2

这个解仍然是 O(n)。实际上，我不完全确定为什么 else 语句会影响这一点。您正在对字符串中的每个字符执行一次操作。

即使对于每个字符，您正在执行多个指令（比较等），您可能认为复杂性类似于 O(3n)，但您当然忽略了系数。我相信您知道这一点，但是对于将来查看此问题、对 else 语句感到困惑的人来说，这可能会有所帮助。

Answer 3

不考虑 if-else 条件，循环遍历字符串的每个字符，因此时间复杂度为 O(n)。