驗證prim算法的上界複雜度

Question

我想知道如何證明Prim算法的時間複雜度的上界。我知道Prim算法的時間複雜度是O（| E | log | V |），其中E是邊，V是頂點，但它是什麼意思的時間複雜度的上限呢？

Answer 1

但是這是什麼意思的時間複雜性的上限呢？

你的問題一般是關於任何算法的上限。 上限限制了最差的情況，比如f（x）「遠」可以走多遠。

功能描述的大O符號通常只提供了函數增長率的上限。算法的上限用於指示上限或最高增長以指示上限或最高增長率。

這意味着給定的算法在給定輸入集的情況下不能比這個複雜度差。

因此，使用圖的二進制堆和鄰接關係並按重量排序邊，總時間複雜度爲O(|E| log |V|)。因此，f(x) = O(|E| log |V|)。

當用Big-O符號表示時，它被限制在該函數下面。