Ruby Anagram 算法的时间和 space 复杂度

Question

我在这里写了这个算法，我正在尝试根据 Big-O 符号来评估它的时间和 space 复杂性。该算法确定两个给定的字符串是否是变位词。

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)，space复杂度是O(1)？我相信我可能会误认为 space 复杂性（可能是 O(n)），因为 selected_index 变量被反复重新分配，这会占用相对于 each_char 多长时间的内存循环运行。

如果有人可以提供一些指导，那就太好了:)

Answer 1

将所有这些评论收集到一个答案中，这是我的分析：

时间

给出的算法确实有 O(n^2) 运行宁时间。

循环体执行 n 次，index 为线性时间，slice 为线性时间，其余为常量时间，总共需要 O(n^2)次。

Space

所呈现的算法需要线性 space，因为它会在每次迭代时更新 str2 的副本。

算法的其余部分只采用常量 space，除非您包括输入本身的存储，这也是线性的。

更快的算法：排序 str1 和 str2

更快的算法是进行字符串比较 sort-by-character(str1) 和 sort-by-character(str2)。这将花费 O(n log n) 时间和 O(n) space 进行排序；和线性时间和常数 space 用于比较，总的 O(n log n) 时间和 O(n) space.

更快的算法：使用散列（由 OP 在评论中提出）

使用哈希表存储字符然后比较字符计数可以将运行宁时间减少到 O(n)，假设标准 O(1) 插入和查找哈希操作。本例中的 space 是哈希表所需的 space，对于大小为 k 的字符字母表，它是 O(k)，如果 [=27]，则可以将其视为常量=] 是固定的。当然，输入参数在传入或最初存储的位置仍然会消耗它们的初始 O(n) space； O(k) 仅反映运行该算法所需的额外 space。

Ruby Anagram 算法的时间和 space 复杂度

Time and space complexity of Ruby Anagram algorithm

ruby

algorithm

time-complexity

big-o

space-complexity