問題描述
如何計算此代碼的時間複雜度？ (How can I compute the time complexity of this code?)
def long_common_prefix(input_list):
for i in range(1, len(input_list)):
input_list[0] = get_prefix(input_list[0], input_list[i])
return input_list[0]
def get_prefix(s1, s2):
p1 = p2 = 0
e1, e2 = len(s1), len(s2)
currLongest = ''
while p1 != e1 and p2 != e2:
if s1[p1] == s2[p2]:
currLongest += s1[p1]
p1 += 1
p2 += 1
else:
break
return currLongest
</code></pre>
這是一個計算列表中字符串的最長公共前綴的代碼。因此，例如，['abcd','abc','ab'] 會給我 'ab'。代碼運行良好，但我不知道如何定義代碼的時間和空間複雜度。
在long_common_prefix中，只有一個循環是O(N)，在循環內部，它調用了幫助器get_prefix。由於 get_prefix 將是 O(N) 並且它將在單個循環內運行，所以它會是 O(N^2) 其中N是字符串的長度？
謝謝。
參考解法
方法 1:
You are right, except N is the length of the input list, but get_prefix operates in linear time (and space) on the strings, and the lengths of the strings is in no way related to the length of the input list.
The complexity of get_prefix is O(M), where M is the length of the common prefix.
Time complexity: O(N*M)
Space complexity: O(M)
(by Dawn17、user10878951)
參考文件