algorithm - 如何找到字谜算法的时间复杂度

Question

前言：这不是一道作业题。我正在阅读 Python 中的算法书。

如果我有以下代码来解决字谜。

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

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

score 2 · Accepted Answer

不，因为你需要做固定的次数，复杂性仍然存在O(n log n)。

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

另请注意，您n的“未定义”：您应该说n是max(a.length, b.length)

score 1 · Accepted Answer

不，它变成O(2*[n log n])，但它与O(n log n)

仍然，你必须比较两个排序的字符串，它的长度是线性的，所以它变成O(n + n log n)，又是nlogn

2 回答 2