变长队列BF算法复杂度分析

Question

我开发了一个算法，它是树上BFS的一种变体，但它包含了一个概率因子。为了检查一个节点是否是我要查找的节点，将执行一个统计测试（关于这个，我将不做太多的详细介绍）。如果测试结果为正，则将节点添加到另一个队列（称为tested）。但是当一个节点没有通过测试时，tested中的节点需要再次测试，因此这个队列被附加到还有待测试节点的队列中。你知道吗

在Python中，考虑到队列q从根节点开始：

...
tested = []
while q:
    curr = q.pop(0)
    p = statistical_test(curr)
    if p:
        tested.append(curr)
    else:
        q.extend(curr.children())
        q.extend(tested)
        tested = []
return tested

由于该算法是概率的，在搜索之后，可能有多个节点位于tested，但这是意料之中的。我面临的问题是试图估计这个算法的复杂性，因为我不能简单地使用BFS的复杂性，因为q和tested的长度是可变的。你知道吗

我不需要一个封闭和明确的答案。我需要的是一些关于如何处理这种情况的见解。你知道吗

Answer 1

最坏的情况是以下过程：

1. All elements 1 : n-1 pass the test and are appended to the tested queue.
2. Element n fails the test, is removed from q, and n-1 elements from tested are pushed back into q.
3. Go back to step 1 with n = n-1

这是一个典型的O（n²）过程。你知道吗