algorithm - geeks - geektogeek




如何有效地配對襪子? (20)

你正試圖解決錯誤的問題。

解決方案1:每次將臟襪子放入洗衣籃時,請將它們系在一起。這樣你洗完後就不用做任何分類了。可以把它想像成在Mongo數據庫中註冊索引。未來可以節省一些CPU。

解決方案2:如果是冬天,你不必穿襪子。我們是程序員。只要它有效,沒有人需要知道。

解決方案3:傳播工作。您希望異步執行這樣一個複雜的CPU進程,而不會阻止UI。把那堆襪子塞進一個袋子裡。只在需要時尋找一對。這樣,它所需的工作量就不那麼明顯了。

希望這可以幫助!

昨天我把乾淨的洗衣店的襪子配對,弄清楚我做的方式效率不高。 我正在做一個天真的搜索 - 挑選一個襪子並“迭代”堆,以找到它的對。 這需要平均迭代n / 2 * n / 4 = n 2/8襪子。

作為一名計算機科學家,我在想我能做些什麼? 當然,為了實現O(NlogN)解決方案,我們會想到排序(根據大小/顏色/ ...)。

哈希或其他非就地解決方案不是一種選擇,因為我無法複製我的襪子(儘管如果可能的話可能會很好)。

所以,問題基本上是:

鑑於一堆n雙襪子,包含2n元素(假設每個襪子只有一對匹配),有效配對多達對數額外空間的最佳方法是什麼? (我相信如果需要,我會記住那些信息。)

我將感謝一個解決以下方面的答案:

  • 大量襪子的一般理論解決方案。
  • 襪子的實際數量並不是那麼大,我不相信我的配偶和我有超過30雙。 (並且很容易區分我的襪子和她的襪子;這也可以使用嗎?)
  • 它是否等同於元素清晰度問題

案例1 :所有的襪子都是相同的(這就是我在現實生活中所做的事情)。

選擇他們中的任何兩個來做一對。 恆定時間。

案例2 :有一定數量的組合(所有權,顏色,大小,紋理等)。

使用基數排序 。 這只是線性時間,因為不需要比較。

案例3 :預先不知道組合的數量(一般情況)。

我們必須進行比較以檢查兩隻襪子是否成對。 選擇一種基於O(n log n)比較的排序算法。

然而在現實生活中,當襪子的數量相對較小(恆定)時,這些理論上最優的算法將不能很好地工作。 它可能比順序搜索花費更多的時間,這在理論上需要二次時間。


作為一個實際解決方案

  1. 快速製作成堆易於辨別的襪子。 (用顏色說)
  2. 每次打樁並使用襪子的長度進行比較。 作為一個人,你可以做出一個相當快速的決定,哪個襪子用於分區,避免最壞的情況。 (您可以並行查看多個襪子,使用它對您有利!)
  3. 當它們達到你可以立即找到斑點對和無法穿著的襪子的門檻時,停止對它們進行分類

如果你有1000個襪子,8種顏色和平均分佈,你可以在c * n時間內製作每堆125襪子4堆。 使用5個襪子的閾值,您可以在6次運行中對每一堆進行排序。 (計算2秒鐘在右側樁上扔襪子,它將花費你不到4小時。)

如果你只有60只襪子,3種顏色和2種襪子(你/你的妻子),你可以在1次運行中對每堆10只襪子進行分類(再次閾值= 5)。 (計算2秒鐘將需要2分鐘)。

最初的存儲桶排序將加快您的進程,因為它在c*n時間內將您的n個襪子劃分為k個桶,因此您只需要執行c*n*log(k)工作。 (沒有考慮到門檻)。 所以你所做的一切都是關於n*c*(1 + log(k))工作,其中c是扔襪子的時間。

與任何c*x*n + O(1)方法相比,該方法將是有利的,大致與log(k) < x - 1一樣長。

在計算機科學中,這可能是有用的:我們有n個東西的集合,它們的順序(長度)以及等價關係(額外信息,例如襪子的顏色)。 等價關係允許我們對原始集合進行分區,並且在每個等價類中,我們的訂單仍然保持不變。 事物到它的等價類的映射可以在O(1)中完成,因此只需要O(n)就可以將每個項目分配給一個類。 現在我們已經使用了我們的額外信息,可以以任何方式對每個班級進行排序。 優點是數據集已經明顯更小。

如果我們有多個等價關係,那麼該方法也可以嵌套 - >製作顏色堆,而不是在紋理上的每個堆分區內,而不是長度排序。 創建具有大於2個元素且具有大約均勻大小的分區的任何等價關係將帶來比排序更快的速度提升(假設我們可以直接將襪子分配到其堆中),並且在較小的數據集上可以非常快速地進行排序。


如果“移動”操作相當昂貴,並且“比較”操作便宜,並且您需要將整個集合移動到緩衝區中,其中搜索比原始存儲快得多...只需將排序集成到強制中移動。

我發現將分揀過程整合到懸掛乾燥使其變得輕而易舉。無論如何我需要拿起每個襪子,然後把它掛起來(移動)而且我沒有任何東西把它掛在琴弦上的特定位置。現在只是不強制搜索整個緩衝區(字符串)我選擇按顏色/陰影放置襪子。更深的左,更亮的右邊,更豐富多彩的前面等等。現在,在我掛下每個襪子之前,如果已經匹配的那個,我會在它的“正確的附近”看 - 這限制了“掃描”到2-3個其他襪子 - 如果它是,我把另一個掛在它旁邊。然後我將它們成對成對,同時在乾燥時從琴弦中取出。

現在這可能與頂部答案提出的“按顏色形成樁”有所不同,但首先,通過不選擇離散樁而是范圍,我可以分類“紫色”是否變為“紅色”或“藍色”堆; 它介於兩者之間。然後通過集成兩個操作(掛起和排序),掛起的排序開銷就像單獨排序的10%。


成本:移動襪子 - >高,找到/搜索襪子 - >小

我們想要做的是減少移動次數,並根據搜索次數進行補償。此外,我們可以利用智人的多線程環境在決策緩存中保存更多內容。

X =你的,Y =你的配偶

從所有襪子的堆A:

選擇兩個襪子,在X線上放置相應的X襪子,在下一個可用位置Y襪子放在Y線上。

直到A為空。

對於每一行X和Y.

  1. 選擇第一個襪子在線,沿著線搜索,直到找到相應的襪子。

  2. 放入相應的成品襪子。

  3. 可選當您在搜索線條時,您正在查看的當前襪子與之前的襪子相同,請執行這些襪子的步驟2。

可選地,對於第一步,你從那條線而不是兩條襪子中拿起兩個襪子,因為緩存內存足夠大,我們可以快速識別襪子是否與您正在觀察的線上的當前襪子匹配。如果你有幸擁有三隻手臂,你可以同時解析三隻襪子,因為主體的記憶足夠大。

直到X和Y都為空。

完成

然而,由於這與選擇排序具有類似的複雜性,所以花費的時間遠遠少於I / O(移動襪子)和搜索(搜索線條的襪子)的速度。


我剛剛完成了我的襪子配對,我發現最好的方法是:

  • 選擇其中一個襪子並將其丟棄(為該對創建一個'桶')
  • 如果下一個是前一個對,則將其放入現有存儲桶,否則創建一個新存儲桶。

在最壞的情況下,這意味著您將擁有n / 2個不同的桶,並且您將確定哪個桶包含當前襪子對的n-2個桶。顯然,如果你只有幾對,這個算法效果很好; 我做了12對。

它不是那麼科學,但它運作良好:)


我所做的就是拿起第一隻襪子並將其放下(比如說,放在洗衣盆的邊緣)。 然後我拿起另一隻襪子,檢查它是否和第一隻襪子一樣。 如果是,我將它們都刪除。 如果不是,我把它放在第一個襪子旁邊。 然後我拿起第三個襪子並將其與前兩個比較(如果它們仍在那裡)。 等等。

假設“刪除”襪子是一種選擇,這種方法可以相當容易地在數組中實現。 實際上,你甚至不需要“移除”襪子。 如果你不需要對襪子進行分類(見下文),那麼你可以只是移動它們,最後得到一個陣列,它在陣列中成對排列所有襪子。

假設socks的唯一操作是比較相等,這個算法基本上仍然是一個n 2算法,雖然我不知道平均情況(從未學會計算)。

排序當然可以提高效率,特別是在現實生活中,您可以輕鬆地在另外兩個襪子之間“插入”襪子。 在計算中,同樣可以通過樹來實現,但這是額外的空間。 而且,當然,我們回到NlogN(或者更多,如果有幾個襪子通過排序標準相同,但不是來自同一對)。

除此之外,我無法想到任何事情,但這種方法在現實生活中看起來確實非常有效。 :)


我推出了另一種解決方案,它不會承諾更少的操作,也不會減少耗時,但應該嘗試看看它是否足夠好,可以在大量的襪子配對中提供更少的時間消耗。

前提條件:不能保證有相同的襪子。如果它們具有相同的顏色,則並不意味著它們具有相同的尺寸或圖案。襪子隨機洗牌。可能有奇數襪子(有些缺少,我們不知道有多少)。準備記住變量“index”並將其設置為0。

結果將有一兩堆:1。“匹配”和2.“缺失”

啟發式:

  1. 找到最有特色的襪子。
  2. 找到它的匹配。
  3. 如果沒有匹配,請將其放在“丟失”堆上。
  4. 從1開始重複,直到沒有更獨特的襪子。
  5. 如果少於6個襪子,請轉到11。
  6. 盲目地將所有襪子與其鄰居配對(不要打包)
  7. 找到所有匹配的對,打包並將包裝對移動到“匹配”堆; 如果沒有新的匹配 - 將“index”增加1
  8. 如果“index”大於2(這可能取決於襪子數量,因為襪子數量越多,盲目配對的機會就越少)轉到11
  9. 洗牌剩下的
  10. 轉到1
  11. 忘記“索引”
  12. 選一個襪子
  13. 找到它的一對
  14. 如果襪子沒有配對,請將其移至“缺失”堆
  15. 如果匹配發現它配對,打包並將其移動到“匹配”堆
  16. 如果還有一個襪子到12個
  17. 如果只有一個去14
  18. 微笑滿意:)

此外,還可以添加檢查損壞的襪子,就像刪除那些。它可以插入2到3之間,以及13到14之間。

我期待著聽到任何經歷或更正。


現實世界的方法:

盡快將襪子從未分類的絨毛上取下,然後放在你面前的絨毛中。樁應安排在一定的空間效率,所有襪子指向相同的方向;樁的數量受到您可以輕鬆到達的距離的限制。選擇要放襪子的絨毛應該 - 盡可能快 - 將襪子放在一堆明顯像襪子上;偶爾的I型(將襪子放在它不屬於的樁上)或II型(當有現成的襪子堆時,將襪子放在自己的樁中)可以容忍錯誤 - 最重要的考慮因素是速度。一旦所有的襪子堆成一堆,快速穿過多襪子堆創建成對並移除它們(這些正朝向抽屜)。如果堆中存在不匹配的襪子,則將它們重新堆疊到最佳狀態(在盡可能快的約束範圍內)堆中。當所有多襪子堆已經處理完畢時,匹配由於II型錯誤而未配對的剩餘可配對襪子。哎呀,你已經完成了 - 我有很多襪子,直到很大一部分髒了才洗它們。另一個實用的注意事項:我將一雙襪子的頂部翻過另一個,利用它們的彈性,使它們在被運送到抽屜和抽屜時保持在一起。


理論極限是O(n),因為你需要觸摸每個襪子(除非一些已經以某種方式配對)。

您可以使用基數排序實現O(n)。 您只需要為存儲桶選擇一些屬性。

  1. 首先你可以選擇(她的,我的) - 將它們分成2堆,
  2. 然後使用顏色(可以對顏色有任何順序,例如按顏色名稱按字母順序排列) - 按顏色將它們分成堆(請記住保持同一堆中所有襪子的第1步的初始順序),
  3. 然後襪子的長度,
  4. 然後紋理,....

如果您可以選擇有限數量的屬性,但有足夠的屬性可以唯一地標識每對,那麼您應該在O(k * n)中完成,如果我們認為k是有限的,則為O(n)。


考慮一個大小為“N”的哈希表。

如果我們假設正態分佈,那麼至少有一個襪子映射到一個桶的“插入”的估計數量是NlogN(即,所有桶都已滿)

我把它作為另一個謎題的一部分,但我很高興被證明是錯誤的。這是我的博客文章

設'N'對應於您擁有的獨特顏色數量/襪子數量的近似上限。

一旦發生碰撞(又名:匹配),只需移除那雙襪子即可。對下一批NlogN襪子重複相同的實驗。它的美妙之處在於,由於人類思維的運作方式,你可以進行NlogN並行比較(碰撞解決)。 :-)


襪子,無論是真正的襪子還是一些類似的數據結構,都將成對供應。

最簡單的答案是在允許分離對之前,該對的單個數據結構應該已經初始化,其中包含指向左右襪子的指針,從而使襪子能夠直接或通過它們的對引用。襪子也可以擴展為包含指向其夥伴的指針。

這通過用抽象層去除它來解決任何計算配對問題。

將相同的想法應用於配對襪子的實際問題,明顯的答案是:不要讓你的襪子不配對。襪子作為一對提供,作為一對放入抽屜(也許通過將它們組合在一起),作為一對穿著。但是,可以在洗衣機中取消配對,所以所需要的只是一種物理機制,可以讓襪子保持在一起並有效地洗滌。

有兩種物理可能性:

對於保持指向每個襪子的指針的“對”對象,我們可以使用一個布袋來保持襪子在一起。這似乎是巨大的開銷。

但是對於每個襪子來保持對另一個的引用,有一個簡潔的解決方案:一個popper(或者如果你是美國人的'按鈕'),例如:

http://www.aliexpress.com/compare/compare-invisible-snap-buttons.html

然後你所做的就是把你的襪子放在一起,然後把它們放在你的洗衣籃裡,然後你再次解決了需要將襪子與“對”概念的物理抽象結合起來的問題。


這是在問錯誤的問題。 要問的正確問題是,為什麼我要花時間整理襪子? 當您重視您選擇的X貨幣單位的空閒時間時,每年的成本是多少?

通常情況下,這不僅僅是任何空閒時間,也就是早上的空閒時間,你可以在床上消費,或者喝著咖啡,或者早點離開並且不會被交通堵塞。

退一步往往是好事,並思考解決問題的方法。

還有一種方法!

找一個你喜歡的襪子。 考慮所有相關特徵:不同光照條件下的顏色,整體質量和耐久性,不同氣候條件下的舒適度和氣味吸收。 同樣重要的是,它們不應該在儲存時失去彈性,因此天然織物是好的,它們應該用塑料包裝。

如果左腳襪和右腳襪之間沒有區別,那就更好了,但這並不重要。 如果襪子是左右對稱的,那麼找到一對是O(1)操作,並且對襪子進行排序是近似O(M)操作,其中M是你家裡的地方數量,你已經散佈著襪子,理想情況下是一些小常數。

如果您選擇左右襪子不同的花式配對,則對左右腳桶進行整桶排序需要O(N + M),其中N是襪子的數量,M與上述相同。 其他人可以給出尋找第一對的平均迭代的公式,但是找到盲搜索對的最壞情況是N / 2 + 1,這對於合理的N來說變得天文數字不太可能。這可以通過使用高級圖像來加速。識別算法和啟發式,用Mk1眼球掃描一堆未分類的襪子。

因此,實現O(1)襪子配對效率的算法(假設對稱襪子)是:

  1. 你需要估計一生中你需要多少雙襪子,或者可能直到你退休並轉移到溫暖的氣候而不需要再穿襪子。 如果你還年輕,你還可以估計在我們家裡都有襪子分揀機器人之前需要多長時間,而整個問題變得無關緊要。

  2. 您需要了解如何批量訂購您選擇的襪子,以及它的成本和交付量。

  3. 訂購襪子!

  4. 擺脫你的舊襪子。

另一個步驟3將涉及比較多年來一次購買相同數量或許更便宜的襪子的成本,並增加分揀襪子的成本,但請相信我的話:批量購買更便宜! 此外,存儲中的襪子以股票價格通脹的速度增加,這比許多投資所獲得的更多。 然後還有存儲成本,但襪子真的不佔用衣櫃頂層的空間。

問題解決了。 所以,只要得到新的襪子,拋棄/捐贈你的舊襪子,並在知道你每天都在為你的餘生節省金錢和時間之後過上幸福的生活。


使用模式作為哈希,創建一個將用於不匹配的socks的哈希表。逐個迭代襪子。如果襪子在哈希表中具有模式匹配,則將襪子從表中取出並成對。如果襪子沒有匹配,請將其放入表中。


我希望我能為這個問題貢獻一些新東西。我注意到所有答案都忽略了這樣一個事實,即有兩個點可以執行預處理,而不會降低整體洗衣性能。

此外,即使是大家庭,我們也不需要承擔大量的襪子。襪子被從抽屜中取出並被磨損,並且在被洗滌之前它們被扔在一個地方(可能是垃圾箱)。雖然我不會把所謂的bin稱為LIFO-Stack,但我認為這是可以安全的

  1. 人們將他們的襪子大致扔在垃圾箱的同一區域,
  2. bin在任何時候都不是隨機的,因此
  3. 從這個箱子頂部取出的任何子集通常都包含一對襪子。

由於我所知道的所有洗衣機的尺寸都有限(無論你要洗多少襪子),洗衣機實際隨機化,無論我們有多少襪子,我們總是有小的子集,幾乎沒有單身。

我們的兩個預處理階段是“將襪子放在晾衣繩上”和“從晾衣繩上取襪子”,我們必須這樣做,以便獲得不僅乾淨而且乾燥的襪子。和洗衣機一樣,晾衣繩是有限的,我認為我們擁有整條線,我們可以看到襪子。

這是put_socks_on_line()的算法:

while (socks left in basket) {
 take_sock();
 if (cluster of similar socks is present) { 
   Add sock to cluster (if possible, next to the matching pair)
 } else {
  Hang it somewhere on the line, this is now a new cluster of similar-looking socks.      
  Leave enough space around this sock to add other socks later on 
 }
}

不要浪費你的時間移動襪子或尋找最佳匹配,這一切都應該在O(n)中完成,我們還需要將它們放在未分類的線上。襪子尚未配對,我們在線上只有幾個相似性簇。在這裡我們有一套有限的襪子是有幫助的,因為這有助於我們創造“好”的簇(例如,如果襪子組中只有黑色襪子,按顏色聚類不是要走的路)

這是take_socks_from_line()的算法:

while(socks left on line) {
 take_next_sock();
 if (matching pair visible on line or in basket) {
   Take it as well, pair 'em and put 'em away
 } else {
   put the sock in the basket
 }

我應該指出,為了提高剩餘步驟的速度,明智的做法是不要隨機選擇下一個襪子,而是從每個簇的襪子後順序拿襪子。兩個預處理步驟都不需要花費更多的時間,而不僅僅是將襪子放在生產線上或籃子裡,無論如何我們必須這樣做,所以這應該大大提高洗衣性能。

在此之後,很容易進行散列分區算法。通常,大約75%的襪子已經配對,留給我一小部分襪子,這個子集已經(有些)聚集(在預處理步驟後我沒有在我的籃子中引入太多熵)。另一件事是剩下的集群往往足夠小,可以立即處理,因此可以從籃子中取出整個集群。

這是sort_remaining_clusters()的算法:

while(clusters present in basket) {
  Take out the cluster and spread it
  Process it immediately
  Leave remaining socks where they are
}

在那之後,只剩下幾個襪子。這是我將以前未配對的襪子引入系統並處理剩餘襪子而沒有任何特殊算法的地方 - 剩下的襪子非常少,可以在視覺上非常快速地加工。

對於所有剩餘的襪子,我假設它們的對應物仍未洗滌並將它們放在下一次迭代中。如果你隨著時間的推移註冊了不成對襪子的增長(“襪子洩漏”),你應該檢查你的垃圾箱 - 它可能會被隨機化(你有貓在那裡睡覺嗎?)

我知道這些算法需要很多假設:一個垃圾箱,它可以作為某種LIFO堆棧,一個有限的普通洗衣機,以及一條有限的正常晾衣繩 - 但這仍適用於大量的襪子。

關於並行性:只要將兩個襪子放入同一個bin中,就可以輕鬆地將所有這些步驟並行化。


我的解決方案並不完全符合您的要求,因為它正式需要O(n)“額外”空間。但是,考慮到我的條件,它在我的實際應用中非常有效。因此我覺得它應該很有趣。

結合其他任務

我的特殊情況是我不使用烘乾機,只需將布掛在普通的布烘乾機上。掛布需要O(n)操作(順便說一句,我總是考慮這裡的裝箱問題),問題本質上需要線性的“額外”空間。當我從桶中取出一個新的襪子時,我試著把它掛在它的一對旁邊,如果它已經掛了。如果它是一對新襪子,我會留下一些空間。

Oracle機器更好;-)

它顯然需要一些額外的工作來檢查是否有匹配的襪子已經掛在某處,它將為計算機O(n^2)提供係數的解決方案1/2。但在這種情況下,“人為因素”實際上是一個優勢 - 我通常可以很快(幾乎O(1))識別匹配的襪子,如果它已經掛起(可能涉及一些難以察覺的腦內緩存) - 認為它是一種Oracle機器中有限的“oracle” ;-)我們在某些​​情況下人類比數字機器具有這些優勢;-)

幾乎擁有它O(n)

因此,將襪子配對的問題與掛布的問題聯繫起來我O(n)免費獲得“額外空間”,並且有一個O(n)及時的解決方案,只需要比簡單的掛布更多的工作,並允許立即訪問完整的一對襪子即使在一個非常糟糕的星期一早上...... ;-)


排序你的n雙襪子的問題是O(n)。在將它們扔進洗衣籃之前,將左邊的一個擰到右邊的那個。取出它們後,你切斷了線程並將每一對放入你的抽屜 - 在n對上進行2次操作,所以O(n)。

現在接下來的問題就是你是否自己洗衣服,而你的妻子是自己洗衣服。這可能是一個完全不同的問題領域的問題。 :)


每當你拿起襪子,把它放在一個地方。然後你拿起的下一個襪子,如果它與第一個襪子不匹配,則將它放在第一個襪子旁邊。如果有,那就有一對。這樣,它有多少組合併不重要,每個襪子只有兩種可能性 - 要么它已經在你的襪子陣列中,要么它沒有,這意味著你將其添加到數組中的某個位置。

這也意味著你幾乎肯定不會在陣列中擁有所有襪子,因為襪子會在匹配時被移除。


這就是我實際操作的方式,對於p雙襪子(n = 2p個別襪子):

  • 從堆中隨意拿一個襪子。
  • 對於第一隻襪子,或者如果所有先前選擇的襪子已經配對,只需將襪子放入您面前的未成對襪子“陣列”的第一個“槽”中。
  • 如果您有一個或多個選定的未配對襪子,請檢查您當前的襪子與陣列中所有未配對的襪子。
    • 在構建陣列時,可以將襪子分為一般類別或類型(白色/黑色,腳踝/工作人員,運動/連衣裙),並“向下鑽取”以僅比較類似。
    • 如果找到可接受的匹配項,請將兩個襪子放在一起並從陣列中刪除它們。
    • 如果不這樣做,請將當前襪子放入陣列中的第一個打開的槽中。
  • 每個襪子都重複一遍。

這種方案最糟糕的情況是每雙襪子都不同,必須完全匹配,而你挑選的前n / 2襪子都是不同的。這是你的O(n 2)場景,而且不可能。如果襪子t的獨特類型的數量小於對的數量p = n / 2,並且每種類型的襪子足夠相似(通常與穿著有關的術語),那麼任何類型的襪子都可以與任何襪子配對其他的,那麼就像我上面推斷,你永遠不會有比較襪子的最大數量是牛逼,在此之後,下一個你拉的意志匹配其中一個不成對的襪子。這種情況在平均襪子抽屜中比最壞情況更可能發生,並且將最壞情況的複雜性降低到O(n * t),其中通常為t << n


這是基於比較的模型的Omega(n log n)下限。(唯一有效的操作是比較兩個襪子。)

假設您知道您的2n襪子是這樣排列的:

p 1 p 2 p 3 ... p n p f(1) p f(2) ... p f(n)

其中f是集合{1,2,...,n}的未知排列。知道這一點不能使問題更難。有n!可能的輸出(第一和第二半之間的匹配),這意味著您需要log(n!)= Omega(n log n)比較。這可以通過分類獲得。

由於您對元素清晰度問題的連接感興趣:證明元素清晰度的Omega(n log n)綁定更難,因為輸出是二進制是/否。這裡,輸出必須是匹配的,並且可能的輸出數量足以獲得合適的界限。但是,有一個變量連接到元素清晰度。假設你有2n襪子,並想知道它們是否可以獨特配對。你可以通過發送從ED的減少(一1,一2,...,一ñ)至(a 1,一1,一2,一2,...,一ñ,一ñ)。 (順便說一下,ED的硬度證明非常有趣,通過拓撲。)

如果你只允許相等的測試,我認為應該有一個Omega(n 2)綁定原始問題。我的直覺是:考慮一個在測試後添加邊緣的圖形,並認為如果圖形不密集,則輸出不是唯一確定的。







matching