Skip to main content
 首页 » 编程设计

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

2025年05月04日9落叶无声

我已经为一个挑战编写了以下解决方案,但我不确定它的时间复杂度:

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)