我正在嘗試計算一個函式的時間復雜度，該函式使用合并排序對兩個陣列進行排序，找到它們的交集并對來自該交集的結果進行排序。
通過分析所涉及的步驟，我發現了具有時間復雜度的關鍵步驟
O(a log a) O(b log b) O(a b) O((a b)log(a b))
其中a是第一個陣列b的大小，是第二個陣列的大小
我進一步簡化為：
O(a log a) O(b log b) O((a b)log(a b))
這就是我卡住的地方。但從我所閱讀的內容來看a b，大于兩者的想法a并b允許我洗掉術語a log a和b log b. 使用它，我得到了整體大 O 表示法O((a b)log(a b))。
我不確定這是否完全正確。
uj5u.com熱心網友回復：
你的分析是正確的。如果您不確定，讓我一步一步更明確地解釋它。
總時間復雜度為：O(alog(a)) O(blog(b)) O(alog(a b) blog(a b)).
對數是 上的嚴格遞增函式，x > 0即log(x) > log(y)iff x > y > 0。
輸入大小不能為負數，因此在我們的分析中我們可以使用這個事實。
使用這個性質，我們知道log(a b) > log(a)，因此alog(a b) > alog(a)。
我們可以得出結論O(a log(a))是 的一個子集，O(a log(a b))因為隨著輸入大小趨于無窮大，每個演算法的上限也是。 因此我們可以擺脫.
對 應用相同的邏輯。
最后，我們有，對應于。alog(a)a log(a b)O(a log(a))O(b log(b))O(alog(a b) blog(a b))O((a b)log(a b))
轉載請註明出處，本文鏈接：https://www.uj5u.com/caozuo/446420.html
上一篇：A*實施