二進制搜索的鄰接列表和平均時間複雜度（2個單獨的問題）

Question

在排序數組和二進制搜索樹中成功執行二進制搜索的平均時間複雜度是否相同，O（log（n））？

另外，是最壞情況下的時間複雜度上是相同的，爲O（n）？

---

爲圖繪製鄰接表時，請問這件事的順序是？例如，那就錯了可以改變：（第一行是如何第2和第3的切換中通知）

要這樣：

Answer 1

最差，平均用於在已排序的數組中搜索O（Log n）。這是因爲如果數組被排序，您最多可以使O（Log n）跳轉來斷定該元素不存在。

在BST中，最差和最平均分別是O（n）和O（Log n），最壞情況發生在樹完全傾斜並因此表現得像鏈表一樣。

---

它們的順序可能你可以執行（如DFS返回到另一個節點不同的路徑）的一些執行但兩者鄰接表表示關係中是完全有效的。