我在閱讀關於java中的Big O表示法時，發現了以下問題，我不明白它們的答案。 （a）最佳算法的最壞情況漸近運行時間是什麼，用於在使用排序數組實現的字典中查找某些內容的最佳算法？ （b）什麼是最佳算法的最佳漸近運行時間，用於在使用排序數組實現的字典中查找某些內容的最佳算法？ （c）最佳算法的最壞情況漸近運行時間是什麼，用於在使用排序鏈接列表實現的字典中查找某些內容的最佳算法？ （d）最佳算法的最佳情況漸近運行時間是什麼，用於在使用排序鏈接列表實現的字典中查找某些內容的最佳算法？ O（1）不同數據結構中的大O表示法
（e）給定一個二叉搜索樹，找到哪個值是最小值並刪除它。 （f）給定一個二叉搜索樹，找到哪個值是中間值，並刪除該值，即 （n）
（f） O（n）
你能向我解釋答案嗎？他們在前四個問題中的具體算法是什麼意思？
感謝
大O是最壞的情況。當你想計算大O時，你需要假定所有東西都會在最後一個項目中找到，天空是黑色的等等。
（a）最好的算法是二分搜索，它在中間猜測排序好的陣列，如果針更大，則猜測後面的元素的中點，否則前者的元素。重複這個操作直到找到該元素或該子集不重要。既然你總是有兩個可能的決定，並且在每一個決定中，這個集合的大小都減半，那麼步驟的數量就會重複你的集合可以減半的次數，這個數字就是2的冪就會產生集合的大小。這是log（n）。最壞的情況是需要執行所有步驟，即O（log（n））。
（b）中，最好的情況是，該項目發生在集，這恰好是第一猜測的中間恰好，因此結果是O（1）。
（c）在鏈表你不能這樣做，即使它是排序的二進制搜索，因爲你只能從一個給定的元素獲得下一個元素。最壞的情況是，針恰好是最後一個。爲O（n）
（d）的情況與上述相同，但最好的情況是，當第一個項目恰好是所搜索的項目。 O（1）
（e）在一個平衡BST搜索時間將是O（logn）時間和去除將是O（1）。但是，如果我們假設最壞的，也就是說，BST是不平衡的根源是最大的，那麼搜索將遍歷所有項目，直到它到達的唯一葉，最低爲O（n），並將其刪除O（1）。（f）要找到BST中的中位數，您可能需要遍歷所有節點，想象一下當根有兩個孩子並且最左邊的孩子只有正確的孩子並且最右邊的孩子只有左孩子和樹的情況總共有兩片葉子。在這種情況下，最糟糕的情況是當你選擇了錯誤的方向並穿越了錯誤的一面，然後必須往好的方向走，以及他最後一個元素是你正在搜索的那個元素。 O（n）
非常感謝你 –
@senshinakamora，不客氣。 –
你的問題具體是什麼？ – Carcigenicate
答案以大O標記告訴你在相應問題中要求的複雜性。前者爲 –
。在前四個問題中，這些特定算法意味着什麼？ –