我写了这个算法,并尝试用大O符号来评估它的时间和空间复杂度。该算法确定两个给定字符串是否为变位词(anagrams)。
def anagram(str1, str2)
str1.each_char do |char|
selected_index = str2.index(char)
return false if !selected_index #to handle nil index
str2.slice!(selected_index)
end
str2.empty?
end
这个函数的时间复杂度是
O(n^2)
,空间复杂度是 O(1)
?我认为空间复杂度可能是 O(n)
,因为selected_index
变量被重复赋值,这将占用内存并与each_char
循环运行的时间相关。如果有人能给一些指导就太好了 :)
O(n)
,因为您通过调用slice
修改了str2
的副本。 - joanisselected_index
对空间复杂度的贡献是否显著?或者这主要来自对对象进行的.slice
调用? - HenryO(n)
,但无论输入大小,最多只有26个字符。因此它是常数时间。 - Henryselected_index =
每次调用只需要O(1)
的空间,我认为这不会是一个问题。 - joanis