列表和最大乘积算法
Algorithm on List and Maximum Product
a) 对于正实数序列X=(x1,x2,...,xn)，我们可以找到一个子序列，该子序列中的元素在O(n)中具有最大乘积.
b) 使用阶数为 O(n) 的算法，我们可以合并 m=sqrt(n) 个排序的序列，整个序列我们有 n 个元素。
为什么我的教授说这两句话是假的？
我阅读了 (a) 的 O(n) 算法：
http://www.geeksforgeeks.org/maximum-product-subarray/
谁能帮帮我？
我不知道第一个陈述，但第二个陈述可以通过以下论证说是假的：
由于有sqrt(n)个序列，每个序列有n个元素，n*sqrt(n)中的元素总数。在最坏的情况下，您需要至少检查每个元素一次以将它们全部合并到一个列表中，这将使时间复杂度至少达到 n*sqrt(n)。如果每个序列中有sqrt(n)个元素，请阅读编辑。
我不太确定第一个，因为你提供的算法是针对整数的，而我们在你的情况下处理的是实数。
编辑：k 个排序数组和 n 个总元素的合并算法将时间复杂度设置为 O(n*log(k))。即使每个序列都有 sqrt(n) 个元素（与上一段中假设的每个元素 n 个相反），时间复杂度仍然是 O(n*(log(sqrt(n)))).
a) 对于正实数序列X=(x1,x2,...,xn)，我们可以找到一个子序列，该子序列中的元素在O(n)中具有最大乘积.
b) 使用阶数为 O(n) 的算法，我们可以合并 m=sqrt(n) 个排序的序列，整个序列我们有 n 个元素。
为什么我的教授说这两句话是假的？
我阅读了 (a) 的 O(n) 算法： http://www.geeksforgeeks.org/maximum-product-subarray/
谁能帮帮我？
我不知道第一个陈述，但第二个陈述可以通过以下论证说是假的：
由于有sqrt(n)个序列，每个序列有n个元素，n*sqrt(n)中的元素总数。在最坏的情况下，您需要至少检查每个元素一次以将它们全部合并到一个列表中，这将使时间复杂度至少达到 n*sqrt(n)。如果每个序列中有sqrt(n)个元素，请阅读编辑。
我不太确定第一个，因为你提供的算法是针对整数的，而我们在你的情况下处理的是实数。
编辑：k 个排序数组和 n 个总元素的合并算法将时间复杂度设置为 O(n*log(k))。即使每个序列都有 sqrt(n) 个元素（与上一段中假设的每个元素 n 个相反），时间复杂度仍然是 O(n*(log(sqrt(n)))).