下面我附上了一段代碼。請你們告訴我下面的代碼如何具有O(n)時間的運行時間。def _height2(self, p): if self.is_leaf(p): return 0
else: return 1 + max(self._height2(c) for c in self.children(p))我無法理解它在O(n)時間復(fù)雜度中是如何工作的。請幫助我學(xué)習(xí)這一點。
1 回答
斯蒂芬大帝
TA貢獻(xiàn)1827條經(jīng)驗 獲得超8個贊
假設(shè)n代表樹中的節(jié)點數(shù)，我們可以觀察到以下情況：
c in self.children(p)永遠(yuǎn)不會產(chǎn)生相同的c兩次：除根之外的所有節(jié)點在某個時刻都將是該c，并且僅一次。所以這段代碼代表每個節(jié)點的恒定時間復(fù)雜度。此外，_height2將為所有節(jié)點調(diào)用一次。對于根，這是初始調(diào)用，對于所有其他節(jié)點，這是遞歸調(diào)用。
所有其他代碼（除了對子節(jié)點的迭代和遞歸調(diào)用之外）表示每個節(jié)點的恒定時間復(fù)雜度。
所以我們的時間復(fù)雜度是O(n) 。
添加回答
舉報
0/150
提交
取消