下面我附上了一段代碼。請你們告訴我下面的代碼如何具有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)時間復雜度中是如何工作的。請幫助我學習這一點。
1 回答
斯蒂芬大帝
TA貢獻1827條經驗 獲得超8個贊
假設n代表樹中的節點數，我們可以觀察到以下情況：
c in self.children(p)永遠不會產生相同的c兩次：除根之外的所有節點在某個時刻都將是該c，并且僅一次。所以這段代碼代表每個節點的恒定時間復雜度。此外，_height2將為所有節點調用一次。對于根，這是初始調用，對于所有其他節點，這是遞歸調用。
所有其他代碼（除了對子節點的迭代和遞歸調用之外）表示每個節點的恒定時間復雜度。
所以我們的時間復雜度是O(n) 。
添加回答
舉報
0/150
提交
取消