Collection.toArray（）的時間複雜度是多少？

方法Collection.toArray()的時間複雜度是多少？它是O（n），如果是，它比循環提供什麼好處，並將列表中的值單獨分配給一個數組（除了漂亮的外觀和當然額外的努力）。Collection.toArray（）的時間複雜度是多少？

'Collections'沒有'toArray'方法。你的意思是'Collection'接口嗎？ – 2014-12-06 03:25:25

謝謝你剛剛編輯它:) – 2014-12-06 05:04:01

因爲toArray()方法是抽象的，談到它的時間複雜度一般是沒有意義的。

但是，對於本機實現，其複雜性的確是O(n)。值得注意的是，Collection是Iterable的子接口。如果實現不能有效迭代的Iterable，那我們是很荒唐的。

toArray()的實施保持開放，留下優化空間的事實。有可能比使用簡單迭代構建數組更快（數組複製，在多個線程中運行...）。但是，AbstractCollection中的default implementaion使用您在問題中提到的確切方法。

2014-12-06 03:27:48 Tregoreg

通用迭代案例應該通常是'nx O（Iterator＃next（））'，但儘管我不知道其中一個，但應該不會太難'next（）'不是O（1）的特殊集合。 – zapl 2014-12-06 03:54:24

@zapl這絕對是真的，但不適用於本機實現，這是我相信OP的想法。 – Tregoreg 2014-12-06 04:02:18

任何集合上的toArray()調用都會遍歷整個集合。對於來自java.util的所有收集，這意味着O（n）定時。當然也可以構造比O（n）慢的實現，但O（n）爲時序提供了一個下界，因爲你必須遍歷整個集合。

當您需要調用專門詢問數組的API時，或者在出於任何原因需要製作集合的副本時，請致電toArray()。一般來說，您不想過度使用toArray()，因爲它會分配足夠的內存以適合您的集合的所有元素。

2014-12-06 03:29:07 dasblinkenlight

回答