我已經為一個挑戰編寫了以下解決方案，但我不確定它的時間復雜度：def ASCIIConversion(string): newStr = '' for chr in string: if chr.isspace(): newStr = newStr + ' ' else: newStr += str(ord(chr)) return newStr程序的復雜度 O(logn) 是不是因為 else 語句？
3 回答
阿晨1998
TA貢獻2037條經驗 獲得超6個贊
最壞情況下的時間復雜度計算如下（假設字符串最大長度為 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)
呼如林
TA貢獻1798條經驗 獲得超3個贊
這個解仍然是 O(n)。實際上，我不完全確定為什么 else 語句會影響這一點。您正在對字符串中的每個字符執行一次操作。
即使對于每個字符，您正在執行多個指令（比較等），您可能認為復雜性類似于 O(3n)，但您當然忽略了系數。我相信您知道這一點，但是對于將來查看此問題、對 else 語句感到困惑的人來說，這可能會有所幫助。
添加回答
舉報
0/150
提交
取消