algorithm - 如何找到anagram Algo的时间复杂度

Question

前言:这不是作业题。我正在阅读一本 Python 算法书。

如果我有下面的代码来解决一个字谜。

Public bool anagram (string a, string b) {
    return sort(a) == sort(b);
}

假设排序算法是合并排序，它是 O(n log n)。由于我必须执行两次，时间复杂度是否变为 O(n^2 log n)？

Answer 1

不，因为您需要执行固定次数，所以复杂度仍然是 O(n log n)。

请注意，您还需要执行一项操作 - 即比较字符串。但是，它是 O(n)，并且 O(n + n log n) 仍然是 O(n log n)。

另请注意，您的 n 是“underdefined”:您应该说 n 是 max(a.length, b.length)