可変長キューBFSのアルゴリズム複雑度解析

Question

私はツリー上のBFSのバリエーションのようなアルゴリズムを開発しましたが、確率的要因が含まれています。探しているノードがノードであるかどうかをチェックするために、統計的なテストが実行されます（これについてあまり詳しく説明しません）。テスト結果が肯定的である場合、ノードは別のキュー（tested）に追加されます。しかし、ノードがテストに失敗すると、testedのノードを再度テストする必要があるため、このキューはまだテストされていないノードがあるノードに追加されます。アルゴリズムは確率的である

... 
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にあるかもしれないが、それが期待されている：キューqは、ルートノードから始まることを考慮すると、Pythonで

、。私が直面している問題は、単純にBFSの複雑さを使うことができないので、このアルゴリズムの複雑さを見積もることです。qとtestedは可変長です。

これについては、明確な回答は必要ありません。私が必要とするのは、このような状況に対処する方法に関するいくつかの洞察です。

Answer 1

最悪のシナリオは、次のプロセスである。

1. 全ての要素1：N-1は、試験に合格し、testedキューに追加されます。
2. 要素Nがテストに失敗し、qから除去され、そしては、n-1 testedから要素はqに押し戻されます。
3. とステップ1に戻るN = N-1

これは古典的なO（N ）プロセスです。