窮舉搜尋算法的時間複雜度
我有套裝 $ S_1={2,10,20,6} $ 和 $ S_2={25,26,20} $ 我想找出哪些數字總和為 32。這很容易通過檢查；6 和 26。這似乎類似於背包問題，但我不是專家。
但是，假設我有 1000 個集合，每個集合有 500 個元素，因此將每個集合中的一個項相加總是會給你一個唯一的值。這要檢查和解決要困難得多，特別是如果集合遵循看起來是隨機的結構（它們將由被弄亂的結構化集合構成，並且幾乎不可能猜測混合和反轉集合）。
因此，唯一的方法必須是窮舉搜尋算法。鑑於我的號碼是 52,485,332，有 $ 1000^{500} $ 可能的選項來看看。確實有一些方法可以縮短這個搜尋時間（比如當一個集合的數字大於你的目標值時，你可以忽略這些數字）。但否則你可能還在看 $ 750^{500} $ 可能的選擇。
那麼，這種搜尋算法的時間複雜度是多少呢？ $ O(n^{k}) $ ， 和 $ n $ 套數和 $ k $ 這些集合中的元素數量？他們必須檢查“所有”可能的術語組合，直到其中一個與給定值匹配。
主要問題似乎是“有多少套？” 和“集合有多大？”。事實上，這些集合也可以是各種大小，而不僅僅是統一的。
我不是密碼學專家；我的研究只是與手頭的想法調情。任何幫助，將不勝感激。
因此，唯一的方法必須是窮舉搜尋算法
正如我在評論中提到的，有一些實用的方法可以用於非大值 $ m $ （和 $ m=52485332 $ 不大）。這是一種這樣的方法的概要（假設所有集合都由非負整數組成）：
- 我們有一個數組 $ A_{n, m+1} $ ; 數組的每個元素 $ A_{a, b} $ 將注意我們如何生成總和 $ b $ 從一開始 $ a $ 集（或 $ \perp $ 如果還沒有找到這樣的方法）。
- 初始化所有元素 $ A $ 至 $ \perp $
- 為了 $ i := 1 $ 至 $ n $ 搜尋元素 $ A_{i-1} $ 對於非 $ \perp $ 元素（並且對於 $ i=1 $ ，第 0 個元素被視為唯一的非 $ \perp $ 元素。對於每個這樣的元素 $ A_{i-1, x} $ ， 放 $ A_{i, x + S_{i,j}} $ 至 $ j $ （對於每個元素 $ S_{i,j} $ 集合的 $ S_i $ ） 如果 $ x + S_{i,j} > m $ ， 忽略它。
- 最後，如果 $ A_{n,m} = \perp $ , 不存在導致總和的子集 $ m $ . 如果是別的，我們可以通過回溯數組來恢復這些術語 $ A $ .
這應該是一種實用的算法，用於在給定參數的情況下恢復術語。
這更多地解釋了為什麼總和的唯一性對大小的影響如此之大，以至於 $ 52485332 $ 變得微不足道（它渴望發表評論）。
當所有和必須唯一時，它們必須產生不同的整數。因為有 $ 500^{1000} $ 可能的總和，還有 $ 500^{1000} $ 不同的整數結果。最低的情況是所有整數 $ 0 $ 至 $ 500^{1000}-1 $ .
例如，
$ S_1 = {0, 1, 2, …, 499} $
$ S_2 = {0, 500, 1000, …, 249500} $
$ S_3 = {0, 250000, 500000, …, 124750000} $
…
$ S_{1000} = {0, 500^{999}, 2500^{999}, …, 499500^{999}} $
將是一種確保結果唯一性的方法。如您所見，數字變得非常大非常快。
在這個特定的範例中，很容易找到結果（只需始終選擇適合從最後一組到第一組的最大數字）。甚至大多數數字是 $ S_3 $ 大於 $ 52485332 $ 因此可以忽略不計。
您可能希望集合中的值相對隨機。在這種情況下，值的範圍必須至少稍大一些。
但是，任何值都極不可能低於或等於 $ 52485332 $ （當你統一選擇 $ 500000 $ 出的值 $ 500^{1000} $ )
正如@poncho 所建議的那樣，動態程式實際上只適用於小數字，它的性能並不比窮舉搜尋（集合數量的線性差異）好多少，因為可以重用的子和是獨一無二的，優勢不考慮其他可能性是不存在的。執行時應該與窮舉搜尋的順序相同。只有當值或大或小以達到目標時才能進行改進，但對於合理的目標而言，這並沒有太大的優勢。
On 可以輕鬆地將子集和問題或背包問題簡化為這個問題，只需使用與您想要求和的數字一樣多次的相同集合。問題在於這不是多項式時間縮減螞蟻，因此不足以證明問題是否為 NP 難題。