我有一個算法，採用DAG圖具有n節點，並且對於每個節點，它在其鄰接節點上執行二進制搜索。據我所知，這將是一個O(n log n)算法，但由於日誌內的n僅對應於節點的鄰接關係，所以我想知道這是否會變成O(n log m)。由m我的意思是m節點毗鄰每個節點（這將直觀和經常遠遠少於n）。大O複雜度O（n日誌n）與O（n日誌m）
爲什麼不是O(n log m)？我會說O(n log m)沒有任何意義，因爲m在技術上並不是輸入的大小，n是。此外，最壞的情況m可能是n，因爲節點可以很容易地連接到所有其他節點。正確？
有兩種情況這裏：
m，相鄰節點的數目由恆定C界，和m，相鄰節點的數目僅受n界，數量節點在第一種情況下，複雜度爲O(n)，因爲Log(C)是一個常量。在第二種情況下，這是O(n*log(n))，因爲你在你的問題解釋的原因（即「m可以n））。
是有道理的，我想也一樣，但想確定。 –
大O符號爲算法的複雜性提供了一個上界，所以由於在最壞的情況下m等於n（正確的n-1），所以正確的複雜度爲O（n log n）。
當然，還有其中一個節點連接到所有其他節點的DAG。另一個例子是DAG，節點編號爲0,1,2 ... n，其中每個節點的邊緣都通向所有更高編號的節點。
有一個先決條件是給出一個取決於多個參數的複雜度估計值 - http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm引號a O（| E | + | V | log（| V |）。在某些情況下，這可能是有用的信息
在最糟糕的情況下每個節點都有n-1個鄰居，這意味着它連接到其他人，但是如果每個節點都這樣，那麼它不會是一個非循環圖。 因此，每個節點的平均鄰居小於n。
邊緣的DAG中的最大數目是：（N-1）N/2
如果我們看一下每一個節點，則其（N-1）/ 2的鄰居的平均值。 因此，在最壞的情況下，您的複雜性仍然會保持爲O（n log n）。
n個節點......但在你的例子中m是多少？ –
如果'n == node degree - 1（它可能發生）O（n log n）將是上限。 – nullpotent
在O-notation中，使用不描述輸入的_size_的變量，而是描述它的其他屬性（例如最大鄰居數）是完全正確的。然而，那麼分析取決於實際瞭解這些屬性。 –