如何查找字謎的時間複雜度Algo

Question

前言：這不是一個家庭作業問題。我正在閱讀Python中的一本書。

如果我有以下代碼來解決anagram。

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)

Answer 2

沒有，就變成O(2*[n log n])，但它一樣O(n log n)

的是，你要比較兩個排序字符串，它的長度是線性的，所以它變成O(n + n log n)，這又是nlogn