Java中的大O符號

Question

嘿，大家可以有人解釋我的大o符號嗎？

Answer 1

1-由於陣列元件可以被隨機訪問（無需從一個小區移動到另一個像鏈表），因此可以說基本上陣列[28]，這是O（1）

2-比較兩個數組列表可以完成的方式，這將導致一個較低的大O但與排序。

您可以使用mergesort或quicksort O（nlg（n））對每個數組列表進行排序，然後比較O（n）中的兩個排序列表。結果是O（nlgn）。

但是另一種算法（無需排序）將遍歷一個數組（n）中的每個元素。然後檢查元素是否是另一個數組（n）（並標記爲正確處理重複項）。後一種算法是O（n^2）。

3-是的。你必須逐個瀏覽整個列表，直到找到所需的元素。

Answer 2

既然你有一個數組，那就意味着連續的內存。這意味着在任何給定索引處的查找都將在一個動作中進行，因爲不需要像在鏈接列表中一樣遍歷。所以它是O（1）。

比較兩個ArrayList對象，沒有排序或排序的A和B是O（n^2），因爲ArrayList A中的每個元素必須與B中的每個元素進行比較。因此，在A中有n個元素， B.這將導致A中的每個元素都需要與B進行n次比較。由於n中有n個元素，即n次比較，O（n^2）。

雖然如果您使用排序算法，它將像排序算法一樣快，例如O（n log n）時間或O（n），具體取決於所使用的排序算法。

搜索未排序數組中的特定目標值的確是O（n）。這是因爲你必須搜索數組中的每個元素來檢查它是否存在。由於列表中有n個元素，這意味着有n個比較。