我正在為一個問題找到一種演算法，其中我有兩組點 A 和 B，其中包含 n 點和 m 點。對于復雜度為 O(n log n) 和 O(m) 的集合，我有兩種演算法，我現在想知道這兩種演算法組合的復雜度是 O(n log n) 還是 O(m)。
基本上，我想知道 m 和 n 之間是否存在某種關系，這會導致 O(m)。
uj5u.com熱心網友回復：
如果 m 和 n 真正相互獨立并且兩個量都不影響另一個，那么運行 O(n log n)-time 演算法和 O(m)-time 演算法的運行時間將是 O(n log n 米）。兩個項都不占主導地位 - 如果 n 與 m 相比變得很大，則 n log n 部分占主導地位，如果 m 相對于 n 很大，則 m 項占主導地位。
如果您知道 m 和 n 如何以某種方式相互關聯，這將變得更加復雜。例如，許多圖演算法使用 m 表示邊數，使用 n 表示節點數。在這些情況下，您有時可以簡化這些運算式，但有時不能。例如，使用斐波那契堆實作 Dijkstra 演算法的成本是 O(m n log n)，與我們上面的相同。
uj5u.com熱心網友回復：
您輸入的大小是x: = m n.
組合演算法的復雜度（如果兩者都在組合演算法中最多執行恒定次數）演算法是：
O(n log n) O(m) = O(x log x) O(x) = O(x log x).
uj5u.com熱心網友回復：
是的，如果m ~ n^n，那么O(logm)= O(nlogn)。
有一個對數公式：
log(b^c) = c*log(b)
編輯：
對于這兩種演算法的組合，Big O總是較大的，因為我們關心的是漸近上限。所以它將取決于 和 的n值m。例如：雖然n^n< m，復雜度是Olog(m)，之后就變成了O(nlog(n))。對于 Big-O 表示法，我們只關心較大的值，所以 if n^n>>>> mthen it is O(nlog(n))，否則 if m>>>> n^nthen it isO(logm)
轉載請註明出處，本文鏈接：https://www.uj5u.com/qukuanlian/514858.html
標籤：算法大哥
下一篇：回文鏈表Python解釋