我已经为一个挑战编写了以下解决方案,但我不确定它的时间复杂度:
def ASCIIConversion(string):
newStr = ''
for chr in string:
if chr.isspace():
newStr = newStr + ' '
else:
newStr += str(ord(chr))
return newStr
程序的复杂度,O(logn),是不是因为else语句?
请您参考如下方法:
最坏情况下的时间复杂度计算如下(假设字符串最大长度为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)
