有什么方法可以将这个O(n^2)算法转换为O(n)算法吗？

Question

我有一个算法，可以扫描一个大的循环数组（data）。在数组的某个特定点，我需要查看过去的值（0 = 最新数据点，n = 最旧数据点），并确定是否存在比当前值低5％的值。我最终编写了一个O（n ^ 2）算法，它可以正常工作，但这不可扩展。

        const int numberOfDataPointsInPast = 1000;
        int numberOfDataPoints = 0;
        for (int i = numberOfDataPointsInPast; i >= 0; i--)
        {
            double targetPoint = data[i] * 0.95;
            for (int j = i + numberOfDataPointsInPast; j > i; j--)
            {
                if (data[j] <= targetPoint)
                {
                    numberOfDataPoints++;
                    break;
                }
            }
        }

你有什么想法可以将这个算法转化为O(n)级别的吗？谢谢！

- Martin

---

问题描述和代码似乎不是在描述同一个东西。 - Svante

numberOfDataPointsInPast 是你的数组大小吗？ - phimuemue

你写道 如果当前值比先前值低5%，但在你的代码中，实际上是在计算数据点的数量。因此存在差异。事实上，你的代码计算的是最后n个数据点之前的n个数据点中，至少比当前参考数据点低5%的数据点数量。 - Frerich Raabe

大家好，这是一个循环缓冲区，所以代码就是这样的。我倾向于认为，对于循环缓冲区，迭代器是最好的工具... - code4life

@Martin，你使用的循环数组实现是什么？能提供个样例或链接吗？ - code4life

Answer 1

在迭代数组时，存储最小值。这需要创建一个min变量，并在每个步骤中执行比较检查。不要将所有先前的值与新值进行比较，而是仅将其与最小值进行比较。

- kgiannakakis

---

@San Jacinto：没有算法可以在不锁定的情况下解决这个问题，不确定你的观点是什么？ - tomdemuyt

这并没有考虑到前1500个值的“窗口”。 - Adrian Regan

他在他的代码示例中已经表明了它，即“numberOfDataPointsInThePast”。 - Adrian Regan

这样做行不通。它没有考虑到1500点的窗口。 - Martin

@Moron 哈哈，说得好。对不起，马丁！我本可以措辞更好，避免所有的歧义 :) - San Jacinto

Answer 2

编辑：

经过进一步思考，可以使用简单的O(n)时间算法，无需RMQ或树（请参见下面我回答的部分）。

给定一个数组A[1...n]和窗口宽度W，需要找到最小的A[i, ...i+W]，给定i。

为此，您需要执行以下操作。

将A[1...n]拆分为大小为W-1的连续块。B1、B2、...B(W-1)。

对于每个块B，维护两个名为BStart和BEnd的块。

BStart[i]=B1，B[2]，...，B[i]的最小值。

BEnd[i]=B[W-1]、B[W-2]、...、B[W-i]的最小值。

对于每个块，这可以在O(W)时间内完成，因此总共需要O(n)时间。

现在给定一个i，子数组A[i...i+W]将跨越两个连续的块，称为B1和B2。

使用B1End和B2Start分别从i到块B1的末尾和从块B2的开头到i+w中找到最小值。

这是O(1)时间，因此总计O(n)。

对于循环数组C[1....n]，您只需要在

A[1....2n]上运行上述操作，这基本上是C连接在一起的两个副本，即A[1...n]=C[1...n]和A[n+1 ... 2n]=C[1...n]

---

以前的写作。

好的。假设我这次正确理解了您的问题...

可以在O(n)时间和O(n)空间内完成。

实际上，可以将窗口大小更改为任何您喜欢的数字，并针对不同元素使其不同，并仍然使其工作！

给定一个数组A[1...n]，可以在O(n)时间和O(n)空间内预处理它，以回答以下形式的查询：在子数组A[i...j]中最小元素的位置是什么？以常数时间！

这被称为区间最小值查询问题。

因此，从理论上讲，可以在O(n)时间内完成。

仅使用树将为您提供O(nlogW)时间，其中W是窗口的大小，并且在实践中可能比RMQ更好，因为我认为隐藏的常数可能会使RMQ更糟。

您可以按如下方式使用树。

从后往前插入W个元素。找到最小值并将其推入堆栈。然后删除第一个元素并插入(W+1)th元素。再次寻找最小值并将其推入堆栈。以此类推。总处理时间为O(nlogW)。

最终，你会得到一个最小值的堆栈，当你第二次按正确顺序遍历数组时，你可以继续弹出这些最小值，直到找到0.95*target。

另外，你的问题不是很清楚，你说它是一个循环缓冲区，但你似乎没有使用长度进行模运算。而且，按照编写的方式，你的算法的复杂度是O(n)，而不是O(n^2)，因为窗口大小是一个常数。

- Aryabhatta

---

当您遇到非常小的元素（比如零）时，它将作为列表头链接并将永远保留在那里，即使它超出了numberOfDataPointsInPast。我有什么误解吗？ - nkrkv

@nailxx: 你只需要知道之前是否有一些元素小于等于0.95*newValue。所以有一个零很棒，不是吗？无论如何，您可以在开始搜索之前以O(n)的时间在_fly_中创建链表，方法是向后遍历数组（与问题中的顺序相反）。 - Aryabhatta

@nailxx，@Martin：根据我现在理解的问题，我已经改变了我的答案。如果可以的话，请让我知道它是否有效... - Aryabhatta

@Martin：我已经简化了算法，现在它是一个简单的O(n)时间复杂度和O(n)空间复杂度的算法。 - Aryabhatta

@Martin：人们花了一些精力来回答你的问题。你至少应该表示一下感谢。无论如何，祝你好运。 - Aryabhatta

Answer 3

我认为在O(n)的时间内解决这个问题是不可能的，因为使用O(n)解决它可以用O(n)排序，而这是不可能的（最小排序复杂度为O(nlogn)）。

编辑 - 将排序简化为此问题

假设对于每个点，可以告诉我们过去有多少点的值小于x％（这里的x为5-但x也可以为0，然后计数将为过去任何较小的点）。

现在-假设您想要对n个元素的数组进行排序。如果您可以在O(n)的时间内获取所有元素过去的较小点数，则如果点a的值大于点b，则点a的计数也将大于点b的计数（因为数组是循环的）。 因此，该问题实际上产生了从值到计数的函数，保留了顺序。

现在-新值介于o和n之间，可以在时间n内排序。

请纠正我是否错误（可能是我一开始就没有理解这个问题）。

- Itay Karo

---

O(n) 是可能的，我个人认为。请查看我的回答。 - Aryabhatta

抱歉，我必须给这个负一分：其中涉及到0.95，而且O(n)是可能的，这与排序无关。你需要找到是否存在某个值<= 0.95 * newValue。你不需要像排序那样找到确切的位置。 - Aryabhatta

但是你假设必须对数据进行排序才能完成任务。这并不一定是正确的。 - San Jacinto

@Itay Ok，非常抱歉。我本意是认为人们说/写的话就是他们的意思。不知怎么搞的，我误解了你的意思。 - San Jacinto

由于我自己误解了问题，我已经取消了投票。 - Aryabhatta

Answer 4

您可以维护一个包含当前“窗口”元素的数组buffArray，该数组中有numberOfDataPointsInPast个元素，并按升序排序。

对于每次迭代：

• 检查当前元素是否小于0.95 * buffArray[0]，如果是，则执行必要的操作。
• 从buffArray中删除超出“窗口”的元素（即第i+numberOfDataPointsInPast个元素）。
• 将新元素（即第i个元素）按排序顺序添加到buffArray中。

我理解这并不是O(N)，但肯定比O(N^2)更有效，因为向已排序的数组添加和删除元素是O(log N)。我怀疑最终效率为O(N log(W)),其中W是numberOfDataPointsInPast。

- nkrkv

---

你太棒了，你先发了帖子。 - Jason S

你的帖子更加整洁，让大家自由选择吧 :) - nkrkv

如果使用数组，则最坏情况下的时间复杂度为O(NW)。O(N logW)是不准确的。 - Aryabhatta

在已排序的数组中查找元素的时间复杂度为O(log N)，添加或删除元素的时间复杂度为O(N)。 - jk.

Answer 5

我想我理解了您的要求... 我将重述问题：

给定：一个大小为K的滑动窗口和一个大小为N>K的数据数组，索引从0到N-1。

计算：统计点j的数量，满足K <= j < N-1，并且集合{data[j-1]、data[j-2]、data[j-3]、... data[j-K]}中至少包含一个值小于等于0.95*data[j]的点。

可以按照以下方式完成：

1. 使用最多具有O(log N)插入/删除成本的数据结构对点{data[0]、data[1]、... data[K-1]}进行排序。

2. 将计数器R初始化为0，将j初始化为K。

3. 检查排序后的数组，看最低点是否小于等于data[j]*0.95；如果是，则增加R。

4. 从排序后的数组中移除data[j-K]，并将data[j]插入排序后的数组。

5. 增加j。

6. 如果j<N，则返回步骤3。

关键在于选择适当的数据结构。我非常确定二叉树会起作用。如果增量插入成本为O(log N)，则总运行时间为O(N log N)。

- Jason S

Answer 6

您可以取过去的前numberOfDataPointsInPast个数据点进行排序，这需要nlog(n)的时间。然后进行二分查找，需要log(n)的时间，找到最低的数据点，使其通过5%的测试。这将告诉您在nlog(n)的时间内，有多少个数据点能够通过测试。

- Joshua

Answer 7

迭代需要从底部开始并递增（保持过去的最小值）。目前，如所发布的算法总是向后查看，而不是向前移动并记住过去的最小值。

随着添加新点，数据点范围只能增加上限或下限。随着下限的降低，保持下限就足够了。任何超过下限/0.95的新点都将被接受（因为下限始终在过去）：

const int numberOfDataPointsInPast = 1000; 
int numberOfDataPoints = 0; 
double lb = NAN;
for (int i = 0; i < numberOfDataPointsInPast; i++) 
{ 
    if ( lb == NAN || data[i] < lb ) {
        lb = data[i];
    }
    if ( data[i] >= lb / 0.95 ) {
        numberOfDataPoints++
    }
} 

- Cade Roux

---

这是另一位发帖者提出的相同解决方案。 - San Jacinto

Answer 8

试试这个：

始终保持对缓冲区内元素的两个指针。一个是遇到的最小值，另一个是下一个最小值（即通过增量得到的下一个最高值）。请记住，这些都是指向缓冲区的指针。

在您通过缓冲区的每个步骤中，确定当前值是否小于或等于min1或min2所指向的值，如果是，则更新min1或min2以指向当前位置。 否则，如果通过指针算术，min1或min2的值在缓冲区中向后1500个位置，您需要确定它是哪一个，并相应地重新调整min1或min2，即min1指向min2并将min2设置为指向当前位置，或者 min2仅设置为指向当前位置。

然后可以通过简单比较确定min1或min2指向的值是否小于当前值的15％...

- Adrian Regan

Answer 9

你有两个选择：

1. 排序 -- O(n log n)

2. 中位数的中位数算法

- J-16 SDiZ