我的 Big O 近似值正确吗？

Question

我有一个算法可以确定两个字符串是否是彼此的排列。代码可以在这里找到：https://jsfiddle.net/bxohcgjn/

N = String A
M = String B
For time complexity, i have: O(N(N logN + M logM))
For space complexity, I have: O(N + M)

N logN = for sorting A
M logM = for sorting B

我知道浏览器的排序实现会改变它，但我假设是快速排序。

只是想看看我的想法是否正确。

Answer 1

关于您的时间复杂度，for 循环（线性顺序）不得乘以两个 sort 的总和。

如果一个算法由 n 个步骤组成，则算法的阶数是它们阶数的总和：

O(alg) = O(step_1) + O(step_2) + ... + O(step_n)

在您的情况下，n = 3（sort 和 for）：

O(is_permutation) = O(sort_A) + O(sort_B) + O(for)
                  = O(n logn) + O(m logm) + O(n)

其中最大的是：

O(is_permutation) = max(O(n logn), O(m logm), O(n))

但是由于您之前测试过，在应用 sort 之前，两个字符串的大小必须相同，在最坏的情况下（这就是您正在分析的情况），只有一个大小，因此，表达式被翻译成：

O(is_permutation) = max(O(n logn), O(n logn), O(n))
                  = max(O(n logn), O(n))
                  = O(n logn)

我的 Big O 近似值正确吗？

Is my Big O approximations correct?

big-o