Ruby 字谜算法的时间和空间复杂度

Question

我写了这个算法，并尝试用大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循环运行的时间相关。如果有人能给一些指导就太好了 :)

- Henry

---

空间复杂度至少为 O(n)，因为您通过调用 slice 修改了 str2 的副本。 - joanis

重新分配 selected_index 对空间复杂度的贡献是否显著？或者这主要来自对对象进行的 .slice 调用？ - Henry

一开始我认为哈希表的时间复杂度是O(n)，但无论输入大小，最多只有26个字符。因此它是常数时间。 - Henry

我本以为 selected_index = 每次调用只需要 O(1) 的空间，我认为这不会是一个问题。 - joanis

同意，如果你考虑一个有限的字母表，它是常数空间。 - joanis

Answer 1

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

时间

按照所展示的算法，确实具有O(n^2)的运行时间。

循环体被执行n次，需要线性时间来处理index和slice以及常数时间来处理其余部分，总共需要O(n^2)的时间。

空间

按照所展示的算法，需要线性空间，因为它在每次迭代中更新str2的副本。

除了输入本身的存储空间是线性的之外，算法的其余部分只需要常数空间。

更快的算法：对str1和str2进行排序

更快的算法是对sort-by-character(str1)和sort-by-character(str2)进行字符串比较。这将花费O(n log n)的时间和O(n)的空间进行排序；并且进行比较需要线性时间和常数空间，总体时间复杂度为O(n log n)，空间复杂度为O(n)。

更快的算法：使用哈希表（在评论中由OP提出）

使用哈希表存储字符，然后比较字符计数可以将运行时间降低到O(n)，假设标准的O(1)插入和查找哈希操作。在这种情况下，空间是哈希表所需的空间，如果k是固定的，则为大小为k的字符字母表的O(k)，可以考虑为常数。当然，输入参数仍然会消耗它们最初传入或最初存储的O(n)空间；O(k)仅反映运行此算法所需的额外空间。

- joanis