你會如何估計這個算法的時間複雜度？

Question

設N =頂點數 M =有向圖G的邊數 。我們以鄰接表的形式存儲邊。 爲了清晰起見，我們假設，Oi是頂點i的outdegree，Ii是頂點i的入度。

的算法如下：

for each vertex i 
    for each vertex j in i's adj.list 
    //do some work 
    for each vertex k in j's adj.list 
     //do some work 

的「做一些工作」基本上在恆定的時間內完成（O（1））我不能導出的N的運行時間的一般表達式， M.能有人解釋如何做到這一點？

撇開： 只是爲了防止「我不會做你的功課」的評論，我正在練習來自CLRS的文本問題（這是22.1-5）。我正在這樣做以瞭解如何估計圖算法的時間複雜度。

Answer 1

我假設算法中提到的每個鄰接列表都是一個傳出邊緣列表。如果代之以傳入和傳出邊緣都被引用，那麼總的工作量將乘以4的常數因子，而不會影響O（）等級。

參考for陳述F1，F2，F3，我們有F1循環N次。 F2循環總數爲O1+O2+... = M次，其中Oi是問題中提到的輸出邊緣度數。每循環F2次F3最多循環N次，最壞情況下的下限沒有那麼小。這導致算法的O（M·N）時間（即，來自F1和F2的O（M），每F3的O（N））。