通过异或 k 找到最大大小 n 的子集
Find a subset of maximum size n with XOR k
我有一个大小为 a = 10⁵ 的数组，其中数字的大小至少为 16 个字节。
现在我必须找到一个异或值等于 k 的子序列。
该子序列的最大长度为 n。 (1 <= n <= 20)
我尝试了 BruteForce，但即使进行了很多优化，它仍然需要比我计算机的使用寿命更长的时间。
网上有很多针对类似问题的解决方案，但是 none 可以在这里应用，我无法找到可以在这里提供帮助的算法或方法。
有人知道比 O(n a^n) 时间复杂度更低的更好解决方案吗？
（请注意，我还在上高中，所以请用我能理解的方式解释一下）
编辑：子序列表示数组的非连续部分（例如 ['a'、'c'、'e'] 是 ['a'、'b', 'c', 'd', 'e'])
看到你的更新后，这个问题表面上很明显O(a^n)——指数时间。这是最难的时间复杂度类.
坦率地说，如您所怀疑的那样，以天真的方式编写来解决此问题的程序将花费非常长的时间。不仅仅是超出计算机的使用寿命，因为 n of 20 将在 10^100 次操作的顺序上产生最坏情况的结果。即使调整为每纳秒多次操作，这个时间量也大得令人难以置信，假设我没有计算错误，这将远远超过宇宙的热寂。换句话说，对于大小为 100,000 的数组上的大小为 20 的序列，您永远无法使用朴素的方法解决此问题。
话虽如此，我不知道是否存在“快速”解决方案。乍一看，这似乎是所谓的“k-xor 问题”。或者更确切地说，如果我们将数组中的每个元素与 k 的值进行异或，那么它应该是一个相同的问题。 “k-xor 问题”似乎在密码学中具有如此重要的意义，以至于一直在不断努力创建纯粹用于处理问题的时间复杂度问题的量子算法。这些解决方案适用于 n 的较小值，例如 3 或 4，而不是 20。即使是非量子解决方案似乎也有时间复杂度 O(a^(n/2)) 数量级的解决方案，这意味着最坏情况下的运行时复杂度仍将按 10^50 次操作的数量级执行，这仍然是一个深不可测的大数.
你说你在读高中，考虑到目前仍在进行前沿研究以改进此类问题的解决方案，我认为你研究效率是不合理的。我希望至少向从事论文工作的研究生水平的研究人员询问此类问题的有效解决方案，而不是高中生。
除非您遗漏或误解了可能会显着降低问题复杂性的重要细节，否则您将无法编写有效的解决方案。期间.
简而言之，我会认为这是允许忽略问题的大小，只编写一个可以处理 a 和 n 的较小值的解决方案。如果您的老师不知何故知道一种快速算法，那么也许他们应该提交一篇研究论文。
我有一个大小为 a = 10⁵ 的数组，其中数字的大小至少为 16 个字节。
现在我必须找到一个异或值等于 k 的子序列。
该子序列的最大长度为 n。 (1 <= n <= 20)
我尝试了 BruteForce，但即使进行了很多优化，它仍然需要比我计算机的使用寿命更长的时间。
网上有很多针对类似问题的解决方案，但是 none 可以在这里应用，我无法找到可以在这里提供帮助的算法或方法。
有人知道比 O(n a^n) 时间复杂度更低的更好解决方案吗？
（请注意，我还在上高中，所以请用我能理解的方式解释一下）
编辑：子序列表示数组的非连续部分（例如 ['a'、'c'、'e'] 是 ['a'、'b', 'c', 'd', 'e'])
看到你的更新后，这个问题表面上很明显O(a^n)——指数时间。这是最难的时间复杂度类.
坦率地说，如您所怀疑的那样，以天真的方式编写来解决此问题的程序将花费非常长的时间。不仅仅是超出计算机的使用寿命，因为 n of 20 将在 10^100 次操作的顺序上产生最坏情况的结果。即使调整为每纳秒多次操作，这个时间量也大得令人难以置信，假设我没有计算错误，这将远远超过宇宙的热寂。换句话说，对于大小为 100,000 的数组上的大小为 20 的序列，您永远无法使用朴素的方法解决此问题。
话虽如此，我不知道是否存在“快速”解决方案。乍一看，这似乎是所谓的“k-xor 问题”。或者更确切地说，如果我们将数组中的每个元素与 k 的值进行异或，那么它应该是一个相同的问题。 “k-xor 问题”似乎在密码学中具有如此重要的意义，以至于一直在不断努力创建纯粹用于处理问题的时间复杂度问题的量子算法。这些解决方案适用于 n 的较小值，例如 3 或 4，而不是 20。即使是非量子解决方案似乎也有时间复杂度 O(a^(n/2)) 数量级的解决方案，这意味着最坏情况下的运行时复杂度仍将按 10^50 次操作的数量级执行，这仍然是一个深不可测的大数.
你说你在读高中，考虑到目前仍在进行前沿研究以改进此类问题的解决方案，我认为你研究效率是不合理的。我希望至少向从事论文工作的研究生水平的研究人员询问此类问题的有效解决方案，而不是高中生。
除非您遗漏或误解了可能会显着降低问题复杂性的重要细节，否则您将无法编写有效的解决方案。期间.
简而言之，我会认为这是允许忽略问题的大小，只编写一个可以处理 a 和 n 的较小值的解决方案。如果您的老师不知何故知道一种快速算法，那么也许他们应该提交一篇研究论文。