前言:这不是一个家庭作业问题。我正在阅读一本用 Python 编写的算法书。
如果我有以下代码来解决字谜问题。
Public bool anagram (string a, string b) {
return sort(a) == sort(b);
}
假设排序算法是合并排序，O(n log n)。由于我必须执行两次，时间复杂度是否会变为O(n^2 log n)？
最佳答案
不，由于您需要执行固定次数，因此复杂性仍然是O(n log n)。
请注意，您还需要执行一项操作 - 即比较字符串。但是，它的复杂度是 O(n)，并且 O(n + n log n) 仍然是 O(n log n)。
另请注意，您的 n 是“未定义的”:您应该说 n 是 max(a.length, b.length)
关于algorithm - 如何找到 anagram 算法的时间复杂度，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/10601862/