首頁(yè) 猿問(wèn) 兩個(gè)不同數(shù)量集合嵌套循環(huán)，怎樣效率高？

兩個(gè)不同數(shù)量集合嵌套循環(huán)，怎樣效率高？

Java

FFIVE 2019-04-05 22:19:36

兩個(gè)不同數(shù)量相互有交集的集合嵌套循環(huán)，判斷元素是否交集并進(jìn)行處理。是大集合在外部循環(huán)效率高，還是小集合在外部循環(huán)效率高？

查看完整描述

4 回答

DIEA

TA貢獻(xiàn)1820條經(jīng)驗(yàn) 獲得超3個(gè)贊

這個(gè)好像跟分配到內(nèi)存有關(guān)系，當(dāng)分配的內(nèi)存不足以將兩個(gè)集合的數(shù)據(jù)都讀入內(nèi)存時(shí)就要涉及到i/o問(wèn)題了，這時(shí)候較大的作為內(nèi)循環(huán)會(huì)比較好，爭(zhēng)取一次將內(nèi)循環(huán)的集合（即較大的集合）整個(gè)讀入內(nèi)存

反對(duì) 回復(fù) 2019-04-23

心有法竹

TA貢獻(xiàn)1866條經(jīng)驗(yàn) 獲得超5個(gè)贊

這個(gè)要看你的集合是不是有序的，如果是無(wú)序的話，他們的時(shí)間復(fù)雜度是一樣的。如果兩個(gè)集合都是有序的話，小集合在外，大集合在里面。你可以在最里面的for循環(huán)中，打印一個(gè)count字段，用來(lái)統(tǒng)計(jì)for循環(huán)了多少次。

反對(duì) 回復(fù) 2019-04-23

揚(yáng)帆大魚(yú)

TA貢獻(xiàn)1799條經(jīng)驗(yàn) 獲得超9個(gè)贊

假設(shè)集合 A 的元素?cái)?shù)為 m，集合 B 的元素?cái)?shù)目為 n，且 m > n。那么兩種循環(huán)下：
最佳情況的時(shí)間復(fù)雜度均為 O(n2) 即 n 的平方，最差情況的時(shí)間復(fù)雜度均為 O(mn)
所以，兩者在時(shí)間復(fù)雜度上是相同的。

反對(duì) 回復(fù) 2019-04-23