在3個數組中搜索常見數字的複雜性

有三個大小爲n的數組a1，a2，a3。函數在這些數組中搜索公共數字。算法是下一個：在3個數組中搜索常見數字的複雜性

foreach n in a1 
    if n is found in a2 
     if n is found in a3 
      return true 

return false

我的猜測是最壞的情況將是下一個：A1和A2是相等的，A3不包含任何A1普通號。

在數組a1中迭代的複雜性將是O（i）。搜索數組a2或a3的複雜性是f（n）（我們不知道它們是如何被搜索的）。我的猜測，總體來說最壞情況的複雜性將是：

爲O（n）= N * F（N）* F（N）= N *（F（N））^ 2

有人告訴我，那是錯誤的。那麼正確的答案是什麼？

來源

2011-10-08 ivan_d

n * f(n) * f(n) = n * (f(n))^2

我被告知這是錯誤的。那麼正確的答案是什麼？

對於給定的算法正確答案：

n * (f(n) + f(n)) = O(n*f(n))

你不要搜索a3陣列f(n)次在a1每個n所以你應該使用+而不是*。

來源

2011-10-08 20:36:49 jfs

如果每次都發現在a2中，該怎麼辦？那麼我們將在a3中搜索它，我們應該瞄準最糟糕的情況 –

@Akram Mellice：如果它每次都在a2中找到：'（f（n）+ f（n））= 2 * f（n）= O（f （n））'常數因子不包含在大O符號中。 – jfs

這個問題本身強調了單純依賴big-O的問題，因爲它排除了常量因素，因爲對於小數據樣本，如果它是「O（n）」，則O（n^4）'可以比'O（n）'更快真的是'K * O（n）'，其中'K'是一個相當大的常量（'K> = n^3'），我相信這就是他們在這個面試問題中真正測試你的知識。 – Seph

IMO最差的複雜度是n.log n。你排序每一個數組然後比較。

來源

2011-10-08 20:27:43

這裏需要注意的重要一點是「找到」函數的運行時間是多少？

有兩個可能的答案：

案例1：如果A2列表和A3列表進行排序，那麼這個函數是登錄N次二進制搜索，所以你得到的n * log（n）的^ 2。如果列表是無序的，則然後每個搜索將花費n次（其中n是每個列表的長度）...並且因此它將是n * n * n = n^3

來源

2011-10-08 20:28:55 jayunit100

對於給定的算法：

的foreach項（N）你通過其他2門陣列（2F（n））的循環..所以這是N * 2F（N）= O（N * F（N ））

順便說一句，做最好的辦法是：
讓你第一陣列中找到項目的數組或哈希。
然後通過其他2個陣列，看看他們是否有已經找到的物品。

將項目保存在數組或散列中，並且查找是O（1）。而你只是通過3個陣列每循環一次，讓你有一個複雜O（最大值{N，F（N）}）

來源

2011-10-08 20:29:19

好了，快回答是O（n^3 ）假設它們都具有相同的長度。最糟糕的情況是，我們在a2的最後位置找到了我們要查找的元素，所以我們將跨越整個數組，並且對於a3也是如此，或者它不在a3中存在。並且這是在A1的所有元素是相同的，通過這一點，我們將必須跨越3個數組的所有時間，假設每個具有長度爲n，則總的複雜性是n階^ 3

來源

2011-10-08 20:30:02

再次，最壞的情況是'3 * n'。他只搜索一件物品。 –

@JimMischel我們有3個循環，第一個橫跨A1，第二個和第三個在A2和A3分別搜索，所以我們已經3圈每個人都可以從1到N，所以它的ñ^ 3不是3 * N。如果在a2中發現n意味着我們將在a2中搜索n，則這可能需要n個比較 –

Ack！我誤解了這個問題。讓我再看一看。 –

地點a2元素爲一組s2和a3元素爲一組s3。這兩種操作在每個陣列的元素數量上都是線性的。然後，遍歷a1並檢查元素是否在s2和s3中。查找是恆定的時間。所以整個算法的最佳實現的複雜度爲：

O(n1 + n2 + n3)

凡n1是a1元素的數量，等等爲n2和n3。換句話說，算法在元素數量上是線性的。

來源

2011-10-08 20:36:50

他沒有要求更快的算法或者更好的算法，他想知道給定算法的複雜程度，有很多不同的方法可以解決這個問題 –

嗯，有時人們需要什麼_need_不是他們想要的_ask for_ :) –

因此，在最壞的情況下，你所描述的，在那裏a1和a2相等，a3不包含任何常見的數字與他人，然後在每個a1你n將搜索a2和a3。

所以看起來運行將正比於2n^2的時間。也就是說，這將是一樣的書寫：

int jcnt, kcnt; 
for (int i = 0; i < n; ++i) 
{ 
    for (int j = 0; j < n; ++j) 
    { 
     ++jcnt; 
    } 
    for (int k = 0; k < n; ++k) 
    { 
     ++kcnt; 
    } 
} 
int total = jcnt+kcnt;

你會發現，total將等於2n^2。

假設，當然，該陣列是無序的。如果a2和a3是有序的，你可以做二進制搜索，那麼這將是2n(log n)。

來源

2011-10-08 20:41:00

在3個數組中搜索常見數字的複雜性

回答

相關問題